Reverse a linked list from position m to n. Do it in-place and in one-pass.

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.

/**
Definition for singly-linked list.

public class Node {
  int val;
  Node next;
  Node(int x) { val = x; }
}
**/

public class Solution {
  public Node reverse(Node head, int m, int n) {

  }
}

This problem is selected from LeetCode.

Solution

The basic idea is first getting to the node at position m, and then reverse the n-m+1 nodes after, and relink the first part,
the reversed part and the third part of the list.

Be careful to some special cases:

When m = n, just return the original list.

When m = 1, remember to set head to the first node of the reversed list part.

public class Solution {
  public Node reverse(Node head, int m, int n) {
    if(m==n) return head;

    Node mCur = head;
    Node mPrev = null;
    
    // 1.move mCur to the correct 
    //   position of m 
    // 2.use mPrev to track the 
    //   previous node of mCur
    while(--m > 0) {
      mPrev = mCur;
      mCur = mCur.next;
  
      n--;
    }
    
    // 1.reverse the n-m+1 nodes
    //   starting from mCur
    // 2.use prev the track
    //   the previous node of
    //   the current node.
    Node prev = null;
    Node cur = mCur;
    while(n-- > 0) {
      Node next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
    }
    
    // 1.now prev is the first node
    //   of the reversed list part.
    // 2.cur becomes the first node after the 
    //   reversed list part
    // 3.mCur becomes the last node of the 
    //   reversed list part
    // EX: 
    // x->x->mPrev mCur<-x<-x<-prev cur->x->null
    
    // link the first part of
    // the list to the start
    // of the reversed list part
    if(mPrev != null)
      mPrev.next = prev;
    
    // link the reversed list part
    // to the third list part.
    mCur.next = cur;
    
    // if mCur is the original head, 
    // the new head becomes the head of
    // the reversed list part.
    if(mCur == head)
      head = prev;
    
    return head;
  }
}

RelatedPost