Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
Solution
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public static void main(String[] args) {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
Solution.reverseBetween(n1, 2, 4);
}
public static ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || head.next == null)
return head;
if (m == n)
return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
// find the node before m-node
ListNode beforeM = dummy;
int count = 0;
while (count != m - 1) {
beforeM = beforeM.next;
count++;
}
// find the n-node
ListNode nNode = beforeM;
while (count != n) {
nNode = nNode.next;
count++;
}
ListNode left = beforeM;
ListNode right = beforeM.next;
ListNode afterNNode = nNode.next;
while (right != afterNNode) {
ListNode tmp = right.next;
right.next = left;
// 将整个链表与 reversed 部分相连
if (left == beforeM) {
left.next = nNode;
right.next = nNode.next;
}
left = right;
right = tmp;
}
beforeM.next = left;
return dummy.next;
}
}