Reverse Linked List II

题目描述

反转链表2：

给定头指针head和两个整数left和right，其中left <= right。反转从left到right的位置，并且返回。

示例：

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

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

解法

解法一：

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    dummy := &ListNode{
        Next: head,
    }
    // 搜索反转范围
    pre, tail := dummy, head
    counts := 1
    for tail != nil && counts < right {
        if counts < left {
            pre = pre.Next
        }
        tail = tail.Next
        counts++
    }
    // 在指定范围内反转
    head = pre.Next
    var next *ListNode
    for head != tail {
        next = head.Next
        head.Next = tail.Next
        tail.Next = head
        head = next
    }

    pre.Next = tail
    return dummy.Next
}