92. Reverse Linked List II

Leetcode Linked List

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

Note: $1 \le m \le n \le$ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

分析

类似反转链表在LeetCode中题目有很多，例如LeetCode 25. Reverse Nodes in k-Group, LeetCode 206. 206. Reverse Linked List。题目要求一次性反转链表的一部分。这道题目考查的还是链表的基本操作。方法是相当直接的。唯一需要注意的是如果要求反转的部分包括链表头部，那么肯定需要加入一个虚拟的节点在链表头部前。基本操作是

1. 找到起始点
2. 从起始点开始到结束点，后面的节点都指向前面的节点
3. 把起始点和结束点指向正确位置

public ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == n) return head;
    ListNode prev = new ListNode(-1), next = null; // previously/next visted ListNode
    ListNode start, end; // the start/end of reverse-part linked list
    ListNode cur = prev, root = cur;

    cur.next = head; // add dummy node;
    int i = 0; // index
    // find the start of the reserve-part linked list
    while (cur != null) {
        if (i++ == m) break;
        prev = cur;
        cur = cur.next;
    }
    start = prev; // the start posiiton of reverse-part linked list

    // reverse the linked list between m to n
    // Output: 1->2<-3<-4 5->NULL, m = 2, n = 4
    prev = cur;
    cur = cur.next; // remove to next node
    while (i <= n) {
        next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
        i++;
    }
    end = prev;

    // reverse m -- n : the endpoint part
    // Output: 1->4->3->2->5->NULL
    start.next.next = next;
    start.next = end;

    return root.next;
}