Reverse Linked List II

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.

Analysis

1. Create a dummy node
2. 初始化3个nodes
   1. Pre: 指向mth node的前一个（固定）
   2. Start：指向mth node（固定）
   3. Then：指向m+1th node（不固定，指向想要移到前面的node）
3. For循环，每次把then指向的node插入到pre和start之间
   1. start.next = then.next
   2. pre.next = then;
   3. then.next = start;
   4. then = start.next;
4. Return dummy.next;

Code

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) {return null;}

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        for (int i=0; i<m-1; i++){
            pre = pre.next;
        }

        ListNode start = pre.next;
        ListNode then = start.next;

        // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
        // dummy-> 1 -> 2 -> 3 -> 4 -> 5

        for (int i=0; i<n-m; i++){
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }

        //after one round
        //1->3->2->4->5; pre=1, start=2, then=4
        //after two rounds
        //1->4->3->2->5; pre=1, start=2, then=5 (finish)

        return dummy.next;
    }
}

Reference

Leetcode

Node

reverse的方法需要记忆