ID: 36; medium; 翻转链表（二）
We have three major steps here:
We first proceed to the (m-1)-th node, which is the node before the m-th node. Then we keep track of both of them.
We reverse from m to n using the same technique used in the classical reverse linked list.
Lastly, do not forget to connect the middle part, i.e., the reversed linked list, with mPrev and cur pointer.
Last updated
Was this helpful?
Was this helpful?
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param head: ListNode head is the head of the linked list
* @param m: An integer
* @param n: An integer
* @return: The head of the reversed ListNode
*/
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || head.next == null)
return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
// 1. proceed to m's previous node
for (int i = 0; i < m - 1; i++) {
if (cur == null) return null;
cur = cur.next;
}
// 2. reverse from m to n
ListNode mPrev = cur;
ListNode mNode = cur.next;
cur = cur.next;
ListNode prev = null, next;
for (int i = m; i <= n; i++) {
if (cur == null) return null;
next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
// 3. connect the lists
mPrev.next = prev;
mNode.next = cur;
return dummy.next;
}
}m = 2, n = 4;
mPrev mNode n
step1: 1------->2------->3------->4------->5------->6
mPrev mNode prev cur
step2: 1 2<-------3<-------4 5------->6
mPrev prev mNode cur
step3: 1------->4------->3------->2------->5------->6