25-09-19 反转链表、两数之和
25-09-20 两两交换链表中的节点
昨天和今天在准备速写带画教学内容，学习进度放缓…
相关链接：代码随想录 |> 206.反转链表|24. 两两交换链表中的节点|1. 两数之和
# 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. 两两交换链表中的节点
中等
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 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
}