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

Original 山大王wld 数据结构和算法 2022-05-09

收录于合集 #算法图文分析 161个

My friends are the most important thing in my life.

朋友是我生命中最重要的部分。

问题描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

非递归解决

这题主要考察的是链表节点的交换，要交换链表的节点首先要搞懂链表节点的断开和连接，之前写过一篇文章，《352，数据结构-2,链表》，图文详细介绍了单向链表，双向链表，还有环形链表的断开和链接。

这道题我们可以人为的把链表分为两组，前面两个节点为一组，后面的为一组，我们首先交换第一组的两个节点，交换完之后把后面的节点再分为两组，继续这样交换下去……，直到不能交换为止。注意，如果能交换，那么原来链表的第二个节点就是我们要返回新链表的头结点。

这里就以示例为例画个图来看下

再来看下代码

 1public ListNode swapPairs(ListNode head) {
 2    //链表至少有2个节点才能交换，否则就不要交换
 3    if (head == null || head.next == null)
 4        return head;
 5    //这里的first，second，third可以参照图中的标注
 6    ListNode first = head;
 7    ListNode second;
 8    ListNode third;
 9    //这个是交换链表之后的尾结点，他的next要指向新交换的链表
10    ListNode preLast = null;
11    //这个只赋值一次，它是要返回的新链表的头结点
12    ListNode newHead = head.next;
13    //如果能交换就继续操作
14    while (first != null && first.next != null) {
15        //给second，third赋值
16        second = first.next;
17        third = second.next;
18        //first和second这两个节点交换
19        first.next = third;
20        second.next = first;
21        //这个时候second就是交换之后新链表的头结点，
22        //如果preLast不为空，说明前面还有交换完成的链表
23        //，要让preLast的next指向新链表的头结点
24        if (preLast != null) {
25            preLast.next = second;
26        }
27        //因为first和second交换之后，first就变成新链表
28        //的尾结点了，把它保存在preLast中
29        preLast = first;
30        //前两个交换了，然后从第3个在继续操作
31        first = third;
32    }
33    //返回新链表
34    return newHead;
35}

递归解决

之前讲过《426，什么是递归，通过这篇文章，让你彻底搞懂递归》，递归有2个条件，一个是终止条件，一个是调用自己，并且要同时具备，所以这题的递归模板很容易写出来。

 1public ListNode swapPairs(ListNode head) {
 2    //终止条件，如果节点为空或者没有后继节点，就不能交换
 3    if (head == null || head.next == null)
 4        return head;
 5
 6    //一些逻辑运算，可有可无，视情况而定
 7
 8    //前面两个节点我们保留不要动，从第3个节点往后开始
 9    //两两交换
10    ListNode newListNode = swapPairs(head.next.next);
11
12    //一些逻辑运算，可有可无，视情况而定
13
14    return 交换之后的链表;
15}

假如使用递归从第3个节点往后的节点全部两两交换了，这个时候我们可以把链表分为3部分，第一个节点，第二个节点和后面交换完成的链表，就是1→2→3，这种形式，我们只要再把1和2位置交换了，那么这道题就完成了。来看下代码

 1public ListNode swapPairs(ListNode head) {
 2    //边界条件判断
 3    if (head == null || head.next == null)
 4        return head;
 5    //从第3个链表往后进行交换
 6    ListNode third = swapPairs(head.next.next);
 7    //从第3个链表往后都交换完了，我们只需要交换前两个链表即可,
 8    //这里我们把链表分为3组，分别是第1个节点，第2个节点，后面
 9    //的所有节点，也就是1→2→3，我们要把它变为2→1→3
10    ListNode second = head.next;
11    head.next = third;
12    second.next = head;
13
14    return second;
15}

交换节点的值

还可以换种思路，因为交换链表的结点需要不停的断开和连接，比较麻烦。所以我们还可以不交换链表的节点，直接交换链表节点的值即可，这样就非常简单了

 1public ListNode swapPairs(ListNode head) {
 2    int first;
 3    ListNode temp = head;
 4    while (temp != null && temp.next != null) {
 5        //直接交换链表节点的值
 6        first = temp.val;
 7        temp.val = temp.next.val;
 8        temp.next.val = first;
 9
10        temp = temp.next.next;
11    }
12    return head;
13}