反转链表 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

进阶： 你可以使用一趟扫描完成反转吗？

思路:

时间复杂度：O(n),空间复杂度O(1)

开头增加一个head2，就可以不讨论left是不是1的情况

代码:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if left == right{
        return head
    }
    head2 := new(ListNode)
    head2.Next = head
    left++
    right++
    var pre1,pre2,next1,next2 *ListNode
    tmp := head2
    for i:=0;i<right;i++{
        if i == left-2{
            pre1 = tmp
            pre2 = tmp.Next
        }else if i== right-1{
            next1 = tmp
        }
        tmp = tmp.Next
    }
    next2 = tmp
    pre1.Next = nil
    next1.Next = nil
    next := merge(pre2)
    pre1.Next = next
    for next.Next != nil{
        next = next.Next
    }
    next.Next = next2
    return head2.Next
}

func merge(head *ListNode)*ListNode{
    var head2 *ListNode
    for head != nil{
        
        tmp := head.Next
        head.Next = head2
        head2 = head
        head = tmp
    }
    return head2
}

代码效率：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2 MB, 在所有 Go 提交中击败了73.90%的用户