Reverse Linked List II Solution by <jasonyin>


  • 0
    J

    Approach #1 In place reverse

    Intuition

    This is similar problem as 206. Reverse Linked List. The difference here is the given start and end point (m, m + n).

    Here will use following example and there are three steps to solve this problem.

    Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

    1. find the node before the one we need to revert as start node (node [1]). Since the head is gonna to change when m==1, so add a dummy node before head.

    [dummy] -> [1] (start) -> [2] -> [3] -> [4] -> [5]

    1. just like the Reverse Linked List Problem, we start to reverse the link list from [2] to [4].

    [dummy] -> [1] (start) -> [2] <- [3] <- [4] __ [5]

    Note: after reverse, the node [4].next is [3], so there's no link between [4] and [5].

    1. connect the link list: [1].next to [4] and [2].next to [5]

    [dummy] -> [1] (start) -> [2] <- [3] <- [4] [5]

    Algorithm

    **Javascript (ES6) **

    var reverseBetween = function(head, m, n) {
        if (!head || m <1 || m >= n) {
            return head;
        }
    
        // add the dummy node
        var dummy = new ListNode(-1);
        dummy.next = head;
        head = dummy;
    
        // move m-1 steps to the previous node of [m]th node
        for (var i=0; i<m-1; i++) {
            head = head.next;
        }
    
        // start to reverse the list
        var pre = head.next, curr = pre.next;
        for (i=0; i< n-m; i++) {
            var next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
    
        // head is still point to [1] in above example and curr is [5]
        // head.next is [2]. head.next.next is [2].next to [5]
        head.next.next = curr;
    
        // pre is [4] now and head is [2]
        head.next = pre;
        head = dummy.next;
        
        return head;
    };
    

    Complexity Analysis

    Time complexity : O(n). n is the length of the list.

    Space complexity : O(1).


  • 0
    C

    Good solution but your naming convention is a little bit confusing.


Log in to reply
 

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