Simple Java solution with clear explanation


  • 226
    A

    Simply just reverse the list along the way using 4 pointers: dummy, pre, start, then

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) return null;
        ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
        dummy.next = head;
        ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing
        for(int i = 0; i<m-1; i++) pre = pre.next;
        
        ListNode start = pre.next; // a pointer to the beginning of a sub-list that will be reversed
        ListNode then = start.next; // a pointer to a node that will be reversed
        
        // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
        // dummy-> 1 -> 2 -> 3 -> 4 -> 5
        
        for(int i=0; i<n-m; i++)
        {
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }
        
        // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
        // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
        
        return dummy.next;
        
    }

  • 6
    A

    @ardyadipta HI,
    can you please explain your logic


  • 0
    A

    @AS11
    r u swapping start and then everytime


  • 11
    C

    Oh man... This is so clean.. My code takes like 60 lines...


  • 2
    C

    Can we use dummy node if it requires in-place?


  • 2
    O

    @CharlesLee "in place" is a controversial subject. In most resources, including LeetCode, it refers constant space, O(1); however some resources use it, unfortunately, as O( log n ). This solution above is O(1) space, because the amount of extra used memory is constant, even if the problem size changes (here, the length of ListNode chain). Therefore, it works in place.

    For reference, see the first 2 paragraphs of this Wiki page:
    https://en.wikipedia.org/wiki/In-place_algorithm


  • 0
    C

    @ozzyy Yes, you are right. "An in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables"


  • 0
    R

    Is the logic of your code moving a node before the node of position m for every iteration?


  • 4
    K

    it's so 666666


  • 0
    Z

    Genius solution with a new LIstNode pointing to the head!


  • 0
    A

    @ardyadipta Absolutely marvellous


  • 1
    T

    6666666666666666666


  • 0
    U

    本当に6666666666


  • 2

    Two phase Java solution:
    First while loop moves cur to index = m;
    Second while loop conduct a normal LinkedList reverse.

       public ListNode reverseBetween(ListNode head, int m, int n) {
            if(head == null) return null;
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode pre = dummy, cur = head;
            int k = 1;
            while(cur.next != null && k != m){
                cur = cur.next;
                pre = pre.next;
                k++;
            }
    
            while(cur.next != null && k != n){
                ListNode preNext = pre.next;
                pre.next = cur.next;
                ListNode next = cur.next;
                cur.next = next.next;
                next.next = preNext;
                k++;
            }
    
            return dummy.next;
        }

  • 0
    S

    @AS11 From my understanding, it basically does two things:

    1. start, which records mNode, bubbles up step by step to where the nNode originally is; start node never change, it is always the mNode;
    2. then, which is always the next node of start (obviously it changes every time), is repeatedly being put to the next position of the pre node ( pre node doesn't change either), so that nodes between pre (not include) and start (include) is always in descending order.

    Hope it helps!


  • 0
    V

    I think it is smart.


  • 0
    Y

    I think the logic is:
    Always insert "then" to the front (pre.next).

    Actually it is the same with reverse linked list.


Log in to reply
 

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