92. 反转链表 II

题目#

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路#

头插

代码#

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if m == n {
        return head
    }

    dummy := ListNode{
        Val:  0,
        Next: head,
    }

    var pre, cur *ListNode
    cur = &dummy
    i := 0

    // 先走到 m-1 的位置
    for ; i < m; i++ {
        if i == m-1 {
            pre = cur
        }
        cur = cur.Next
    }

    // 在 m-n 区间内做处理
    for ; i >= m-1 && i <= n-1; i++ {
        // 存一下
        tmp := cur.Next
        // 断链
        cur.Next = cur.Next.Next

        // 头插（放在 m-1 之后）
        tmp.Next = pre.Next
        pre.Next = tmp
    }

    return dummy.Next
}