• 时间：2022-05-16
• 题目序号：24
• 难度：中等

问题描述

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

来源：力扣（LeetCode）

示例1

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

示例2

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

示例3

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

提示

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

解题思路

题解部分参考自LeetCode题解。如有侵权，请联系进行删除~~

• 本题主要就是模拟链表中结点交换的过程
• 由题目示例可知，我们需要对链表中无结点、只有一个结点同样做出处理

• 可以加入虚拟头结点来简化操作（不加虚拟头结点需对头结点单独处理，因为没有前一个结点指向头结点）

创建虚拟头结点后，还需要3个指针来辅助完成交换操作

• p结点指向需要交换的两个结点的前一个结点
• a每次为需要交换的第一个结点，b为需要交换的第二个结点
• 首先让p.next = b
• 再让a.next = b.next
• 最后让b.next = a即可

注意：交换顺序不能乱，否则会断开某些结点之间的连接，可以配合上图理解一下

• 当每次交换完成之后，将p结点指向a结点（下次需要交换的两个结点的前一个位置）

代码实现

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dum = new ListNode(-1);
        dum.next = head;      // 设置虚拟头结点
        ListNode p = dum;
        while(p.next != null && p.next.next != null){     // 链表为空或者只有一个结点时不作处理
            ListNode a = p.next;
            ListNode b = a.next;
            p.next = b;
            a.next = b.next;
            b.next = a;
            p = a;
        }
        return dum.next;
    }
}

总结

• 涉及到链表指针的操作时，需要注意顺序问题
• 顺序不正确的话，可能会导致链表不再连通
• 使用虚拟头结点可以让首结点由特殊结点转化为一般结点，可以简化问题