链表 - 两两交换链表中的节点

链表 - 两两交换链表中的节点

这里我们以力扣24题为例，讲讲如何将相邻的两个节点进行交换

从官方给的示例和我的示例就可以发现：链表的节点数是奇数时最后一个节点交换，是偶数时最后一个节点需要交换

在这里我们还是要用虚拟头节点

接下来我们来梳理下循环中的操作步骤

1. [current]节点初始化成虚拟头节点
2. [current]节点的Next直接指向第三个节点（包括虚拟头节点）
3. 第三个节点的Next指向第二个节点
4. 第二个节点的Next指向第四个节点
5. [current]节点指向第二个节点

注意：上述步骤梳理，以虚拟头节点为第一个节点；所说的第几个节点都是按照原始链表的顺序。

在上述步骤梳理中，还是有很多细节的。

1. 如果虚拟头节点的Next指向第三个节点，就表示第一个节点和第二个节点之间的联系断了
2. 如果第三个节点的Next指向第二个节点，就表示第三个节点和第四个节点之间的联系断了

所以我们在开始交换之前将第二个节点和第四个节点缓存起来。

好，循环体内交换逻辑梳理出来了，那循环条件是什么呢？

文章最开始，我们说了，奇数个节点和偶数个节点的处理是不一样的。又加上我们使用了虚拟头节点，最后总结出循环条件是[current.Next != nil && current.Next.Next != nil]

• 当我们的节点数是偶数，到最后一个节点就停止，最后一个节点的特征是他的Next = nil
• 当我们的节点数是奇数，到倒数第二个节点就停止，此时current就是落在倒数第二个节点上，此时他的特征就是Next.Next = nil

接下来我们就用代码实现了

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    // 构建虚拟头节点
    dummy := &ListNode{
        Next: head,
    }
    current := dummy // 从虚拟头节点开始
    // 控制好循环条件，必须是这个顺序，否则会报空指针异常
    // 其实很好理解，父节点都没有，哪里有子节点
    for current.Next != nil && current.Next.Next != nil {
        temp1 := current.Next // 记录第二个节点
        temp2 := current.Next.Next.Next // 记录第四个节点
        current.Next = current.Next.Next
        current.Next.Next = temp1
        temp1.Next = temp2
        current = temp1 // 这一步需要好好理解下
    }
    return current.Next // 因为我们加上了虚拟头节点，所以最后返回的结果需要去除这个节点
}