反转链表 II

1. 题目描述

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

2. 思路

3. 实现

3.1. 三指针

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    // 找到left的前一个节点
    dummyHead := &ListNode{Next:head}
    current := dummyHead
    for i := 1; i < left; i++ {
        current = current.Next
    }
    // 先保存下一个节点，这个节点就是[left,right]反转之后的尾节点
    next := current.Next
    if next != nil {
        current.Next,next.Next = reverse(next, right-left+1)
    }
    return dummyHead.Next
}

func reverse(head *ListNode, count int) (*ListNode, *ListNode) {
    var prev *ListNode
    current := head
    var next *ListNode
    for i := 0; i < count; i++ {
        next = current.Next
        current.Next = prev
        prev = current
        current = next
    }
    newHead := prev
    newTailNext := current
    return newHead, newTailNext
}

4. 参考

• 92. 反转链表 II - 力扣（LeetCode）