92_reverse_linked_list_ii

92. 反转链表 II 中等

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

代码参考：

package main

import "fmt"

func main() {
    fmt.Println(reverseBetween(newList([]int{1, 2, 3, 4, 5}), 2, 4))
}

// 更具普遍意义的反转链表，记得借助哑节点以防 head 丢失
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    dummy := &ListNode{Next: head}
    i := 1
    pre, cur := dummy, head
    for i < m {
        pre = pre.Next
        cur = cur.Next
        i++
    }

    // 开始反转
    newStart := &ListNode{Val: cur.Val}
    for i < n {
        cur = cur.Next
        newStart = prepend(newStart, cur.Val)
        i++
    }
    cur = cur.Next
    pre.Next = newStart

    // 反转完毕，把 [n...] 之后的接上
    for i := 0; i < n-m; i++ {
        newStart = newStart.Next
    }
    newStart.Next = cur

    return dummy.Next
}

func prepend(head *ListNode, v int) *ListNode {
    node := &ListNode{Val: v}
    if head == nil {
        return node
    }
    node.Next = head
    return node
}