Share my Java code


  • 25
    L

    The basic idea is to build a sub-list when we hit Node m by adding the subsequent nodes to the head of the sub-list one by one until we hit Node n. Then connect the nodes before Node m, the sub-list and the nodes following Node n.

    public ListNode reverseBetween(ListNode head, int m, int n) {
    	ListNode dummyhead = new ListNode(0);
    	dummyhead.next = head;
    	ListNode sublisthead = new ListNode(0);
    	ListNode sublisttail = new ListNode(0);
    	int count = 1;
    	ListNode pre_cur = dummyhead, cur = head;
    	while(count <=n){
    		ListNode temp = cur.next;
    		if (count < m)
    			pre_cur = cur;
    		else if (count == m){
    			sublisttail = cur;
    			sublisthead.next = cur;
    		}else if (count > m){
    			cur.next = sublisthead.next;
    			sublisthead.next = cur;
    		}
    		cur = temp;
    		++count;
    	}
    	pre_cur.next = sublisthead.next;
    	sublisttail.next = cur;
    	return dummyhead.next;
    }

  • 1
    L

    is sublist method in-place as well? I am just wondering, otherwise the method looks great...


  • 0
    L

    Actually the sublist is just cut from the original list, no extra space is used and the nodes between m and n are linked to the sublist directly. So I think it is in-place.


  • 0
    T

    Thanks for your post. Here is my java code based on your idea:

    
    public static ListNode reverseBetween(ListNode head, int m, int n) {
    	        ListNode start = new ListNode(0);
    		start.next = head;
    		ListNode tail = null;
    		ListNode beforeHead = start;
    		for (int i = 1; i <= n; i++) {
    			if (i < m) {
    				beforeHead = head;
    				head = head.next;
    			} else if (i == m) {
    				tail = head;
    			} else {
    				beforeHead.next = tail.next;
    				tail.next = tail.next.next;
    				beforeHead.next.next = head;
    				head = beforeHead.next;
    			}
    		}
    		return start.next;
        }
    

  • 0
    C

    Here is my Java code based on your idea, I think it is more clearly.

    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        
        // tail1 is the (m-1)th node
        ListNode tail1 = newhead;
        int i = 1;
        while (i < m) {
            head = head.next;
            tail1 = tail1.next;
            i++;
        }
        
        // tail2 is the mth node
        ListNode tail2 = head;
        head = head.next;
        i++;
        
        while (i <= n) {
            tail2.next = head.next;
            
            // insert head after tail1
            head.next = tail1.next;
            tail1.next = head;
            
            head = tail2.next;
            i++;
        }
        
        return newhead.next;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.