反转链表
#LeetCode#算法#反转链表 2023-12-31

反转链表

前言

看的灵神视频，整理了一下反转链表（力扣 206）与部分反转（力扣 92）。

正常反转（即整个链表都反转）

Leetcode 206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路

  1. 定义当前遍历到的节点 cur
  2. 定义当前节点的上一个节点 pre，也就是 cur 的上一个节点（反转后就是它的下一个节点），初始时为空，因为头节点的下一个节点应该是空的（换句话说，头节点变成了尾节点）
  3. 遍历给定链表，在每次遍历中，执行以下操作
    1. 定义一个临时变量 next，记录当前节点 cur 的下一个节点。
    2. 使当前节点 cur 的下一个节点指向 pre（反转）
    3. 使 pre 指向当前节点。
    4. 当前节点 cur 指向 next（也就是这个节点本来指向的下一个节点）
  4. 遍历结束后，pre 指向最后一个节点（也就是现在的头节点），cur 指向空。
  5. 返回 pre 即为答案

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func reverseList(head *ListNode) *ListNode {
    // 现在遍历到的节点
    cur := head
    // 它前面的节点，也就是反转后 cur 的下一个节点
    var pre *ListNode
    for !(cur == nil){
        // 原来的下一个节点是
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

部分反转

Leetcode 92. 反转链表 Ⅱ

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

思路

大体思路与反转链表同。

  1. 定义哨兵节点 dummy，dummy 的下一个节点指向 头节点
  2. 定义节点 p0， p0 等于 dummy
  3. 操作 p0，使 p0 等于位置 left 的上一个节点。
  4. cur 指向 p0 的下一个节点（也就是位置 left 的节点）
  5. 从 left 开始，遍历到 right 的位置。在遍历中：
    1. 定义一个临时变量 next，记录当前节点 cur 的下一个节点。
    2. 使当前节点 cur 的下一个节点指向 pre（反转）
    3. 使 pre 指向当前节点。
    4. 当前节点 cur 指向 next（也就是这个节点本来指向的下一个节点）
  6. p0.Next.Next 指向 cur（也就是反转前 right 位置的下一个节点）
  7. p0.Next 指向 pre（也就是反转前 right 位置）
  8. 返回 dummy.Next（头节点）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    // 哨兵
    var dummy = &ListNode{}
    dummy.Next = head
    p0 := dummy
    // 找到翻转第一个节点的前一个结点
    for i := 0; i < left-1; i++{
        p0 = p0.Next
    }

    var cur = p0.Next
    var pre = &ListNode{}
    for i := left; i <= right; i++{
        var nxt = cur.Next
        cur.Next = pre
        pre = cur
        cur = nxt
    }

    p0.Next.Next = cur
    p0.Next = pre
    

    return dummy.Next
}

其他题目类似。