Question
Formatted question description: https://leetcode.ca/all/92.html
92 Reverse Linked List II
Reverse a linked list from position m to n. Do it inplace and in onepass.
For example:
Given 1>2>3>4>5>NULL, m = 2 and n = 4,
return 1>4>3>2>5>NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
@taglinkedlist
Algorithm
Take the example in the title, the three points that are transformed are 2, 3, and 4
. We need to find the first node before the transformation node, as long as the pre is moved backward by m1
steps.
Why do you want to subtract 1, because the problem is counting from 1, here only one step is taken, which is node 1, and use pre to point to it. What if the node 1 starts to change? This is why we use the dummy node. Pre can also point to the dummy node. Then the exchange is about to begin. Since only two nodes can be exchanged at a time, we follow the exchange sequence as follows:
1 > 2 > 3 > 4 > 5 > NULL
1 > 3 > 2 > 4 > 5 > NULL
1 > 4 > 3 > 2 > 5 > NULL
This problem is a followup problem for problem 206. In this problem, only the nodes from position m to n should be reversed, and the reverse operation should be done in onepass. The iterative solution for problem 206 can be adapted here, with some modification.
Obviously, if the list is null, or there is only one element in the list, or position m
is the same as position n
, then no reverse needs to be done and just return the original list.
Since the head may also be reversed, create a dummyHead
whose next pointer points to head
. Find the reverse start node, the reverse end node, the last node before reverse and the first node after reverse, and then do the reverse operation.
For example, for linked list 1>2>3>4>5>NULL
, m = 2, n = 4, the reverse start node is 2, the reverse end node is 4, the last node before reverse is 1, and the first node after reverse is 5.
Like the iterative solution for problem 206, use two pointers prev
and curr
to do the iteration. After the loop, set the last node before reverse to point to the reverse end node (which is the start of the reverse part after reverse), and set the reverse start node (which is the end of the reverse part after reverse) to point to the first node after reverse.
Finally, return dummyHead.next
.
Code
Java

import java.util.Stack; public class Reverse_Linked_List_II { /** * Definition for singlylinked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution_optimize { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummy = new ListNode(0); ListNode prev = dummy; // I missed this one prev.next = head; ListNode p = head; for (int i = 1; i < m; i++) { prev = p; p = p.next; } // @note:@memorize: now p is pointing to mth node ListNode originalFirst = p; for (int i = m; i < n; i++) { ListNode currentHead = prev.next; ListNode futureHead = originalFirst.next; // swap // prev.next = currentHead.next; prev.next = futureHead; // currentHead.next = futureHead.next; originalFirst.next = futureHead.next; futureHead.next = currentHead; } return dummy.next; } } public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (m > n) { return reverseBetween(head, n, m); } int diff = n  m; if (diff == 0) { return head; } ListNode p1 = head; // set diff for both pointers // @note: corner case: nm > listlength while (diff > 0 && p1 != null) { p1 = p1.next; diff; } ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; ListNode p2 = head; int mm = m; while (mm  1> 0) { prev = prev.next; p1 = p1.next; p2 = p2.next; mm; } ListNode nextRecord = p1.next; diff = n  m; // start reverse from p1 to p2 // 1>2>3>4>5 Stack<ListNode> sk = new Stack<>(); while (p2 != p1.next) { // @note: here, when p1==p2 should enter loop sk.push(p2); p2 = p2.next; } while (!sk.isEmpty()) { prev.next = sk.pop(); prev = prev.next; } prev.next = nextRecord; return dummy.next; } } }

// OJ: https://leetcode.com/problems/reverselinkedlistii/ // Time: O(N) // Space: O(1) class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { ListNode dummy, *p = &dummy; dummy.next = head; for (int i = 1; i < m; ++i) p = p>next; auto q = p>next, tail = q; for (int i = m; i <= n; ++i) { auto node = q; q = q>next; node>next = p>next; p>next = node; } tail>next = q; return dummy.next; } };

# Definition for singlylinked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseBetween(self, head, m, n): """ :type head: ListNode :type m: int :type n: int :rtype: ListNode """ def reverse(root, prep, k): cur = root pre = None next = None while cur and k > 0: next = cur.next cur.next = pre pre = cur cur = next k = 1 root.next = next prep.next = pre return pre dummy = ListNode(1) dummy.next = head k = 1 p = dummy start = None while p: if k == m: start = p if k == n + 1: reverse(start.next, start, n  m + 1) return dummy.next k += 1 p = p.next