Description

Reverse Linked List II

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

遍历一次将链表的第m至n个结点翻转。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    slow := &ListNode{
        Next: head,
    }
    fast := slow.Next
    head = slow

    for i := 1; i < m; i++ {
        fast = fast.Next
        slow = slow.Next
    }

    // start指向第一个需要翻转的位置
    pre, start := slow, fast

    // 进行翻转
    // 1. 将fast.Next倒转，指向slow
    // 2. 同时fast和slow前进一步
    for i := m; i <= n; i++ {
        fast.Next, fast, slow = slow, fast.Next, fast
    }

    pre.Next = slow
    start.Next = fast

    return head.Next
}