25-09-19 反转链表、两数之和 25-09-20 两两交换链表中的节点 昨天和今天在准备速写带画教学内容，学习进度放缓… 相关链接：代码随想录 |> 206.反转链表|24. 两两交换链表中的节点|1. 两数之和

206.反转链表

206. 反转链表

简单

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

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]

• -5000 <= Node.val <= 5000

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

双指针法

写的时候犯了个小错误，由于基础不牢，不知道怎么直接给 prev nil，然后直接写了 prev := &ListNode{} 再赋值成 nil ，然后这个节点被丢弃掉，等待 GC 回收。多了一次无意义的分配。

应该是： var prev *ListNode

含义：声明了一个指针，初始状态是「空指针」，不指向任何元素。

这证明我对结构体的传递还不熟悉。

大致过程：

prev = nil

cur = head

tmp = cur.Next // tmp 存储下一个节点，防止指针反向后丢失

cur.Next = prev // 指针反向

以上就是一次反向的过程，遍历的条件是

for cur != nil {

}

如下图所示：

多次操作后…到达最后一次

当 cur == tail 时是最后一次迭代，接着 cur = nil ，不进循环，tmp 也是 nil。此时 return prev 就是反转后的链表

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    // prev := &ListNode{}
    // prev = nil
    var prev *ListNode
    cur := head

    for cur != nil {
        tmp := cur.Next // 存储下一个节点/nil
        cur.Next = prev // 反转指向
        // 向后移动
        prev = cur
        cur = tmp
    }
    return prev
}

24. 两两交换链表中的节点

24. 两两交换链表中的节点

中等

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

虚拟头结点

一定要画图

设一个虚拟头结点指向 head ，然后按照上图的步骤操作。注意这里需要设一个 tmp 存一下节点1。

同时需要注意循环条件。

当链表节点数为偶数时，cur.Next != nil （空链表时也满足）；

当链表节点数为奇数时，cur.Next.Next != nil ；

写循环条件时，cur.Next != nil 应该写在 cur.Next.Next != nil 前面，否则可能会操作空指针。

for cur.Next != nil && cur.Next.Next != nil {
}

完整代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    DummyHead := &ListNode{Next: head}
    cur := DummyHead

    for cur.Next != nil && cur.Next.Next != nil {
        tmp := cur.Next
        cur.Next = tmp.Next
        tmp.Next = cur.Next.Next
        cur.Next.Next = tmp

        // 移动 cur
        cur = cur.Next.Next
    }
    return DummyHead.Next
}