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.
- 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]
- 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].
- 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).