反转链表 II

题目链接:

解题思路：

遍历链表，找到left对应的节点的前一个节点pre
因为要把left到right这段翻转，因此我们不能直接把left进行移动，而是把left的Next进行移动，这样我们翻转完left的Next就是right的Next
翻转的过程中，不断取出left的Next，并插入到pre的后头

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    resNode:=new(ListNode)
    resNode.Next=head
    pre:=resNode
    // 查找到left前一个节点
    for i:=0;i<left-1;i++{
        pre = pre.Next
    }
    cur:=pre.Next
    for i:=left; i< right;i++{
        // 不断取出left后一个元素插入到pre后面，并left的next往后移一位
        next := cur.Next
        cur.Next = next.Next
        next.Next = pre.Next
        pre.Next = next
    }
    return resNode.Next
}

复杂度分析

时间复杂度： 只遍历了一遍链表，因此时间复杂度为 $O(n)$ ，其中 $n$ 是链表的长度
空间复杂度： 空间复杂度为 $O(1)$

上一页复制带随机指针的链表下一页删除链表的倒数第 N 个结点

最后更新于1年前

这有帮助吗？

解题思路：

遍历链表，找到left对应的节点的前一个节点pre

因为要把left到right这段翻转，因此我们不能直接把left进行移动，而是把left的Next进行移动，这样我们翻转完left的Next就是right的Next

翻转的过程中，不断取出left的Next，并插入到pre的后头

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    resNode:=new(ListNode)
    resNode.Next=head
    pre:=resNode
    // 查找到left前一个节点
    for i:=0;i<left-1;i++{
        pre = pre.Next
    }
    cur:=pre.Next
    for i:=left; i< right;i++{
        // 不断取出left后一个元素插入到pre后面，并left的next往后移一位
        next := cur.Next
        cur.Next = next.Next
        next.Next = pre.Next
        pre.Next = next
    }
    return resNode.Next
}