算法力扣刷题记录九【24. 两两交换链表中的节点】

前言

链表操作：力扣【24. 两两交换链表中的节点】
继续。

---

题目阅读

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

---

二、第一次尝试

初始思路：不修改节点内部的值，说明要改指针指向。

和之前改变节点指针同样套路，需要辅助pred和cur来记录位置。进行交换。
整个过程：单看文字描述不太容易理解，可以辅助画图，感受指针方向的改变。

• 分析流程

  • 首先不考虑head=nullptr——传入空指针和head->next=nullptr——只有一个节点的情况。因为可以直接return head。如果通用流程不包含时，再单独添加。
  • 以[1,2,3,4,5,6]示例作讲：
    • 当1和2交换时，第一步记录3的位置，第二步把2的指针指向1，第三步把1的指针指向3。
    • 当3和4交换时，发现1的指针改向4，第二步把4的指针指向3（记录5的位置，不然找不到），第三步把3的指针指向5。
    • 当5和6交换时，发现3的指针改向6，第二步把6的指针指向5（记录6的位置，不然找不到），第三步把6的指针指向6的下一位。
  • 找到规律了。发现改向是要跨节点操作。直接用辅助指针pred，tmp，cur记录位置。然后再补充特殊情况。

• 代码实现，通过测试。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr){//补充空链表和一个节点的情况
            return head;
        }
        ListNode* cur = head->next->next;	//初始指向第三个节点。所以需要head!=nullptr和head->next != nullptr
        ListNode* pred = head;	           //需要二次改向的指针，初始指向第一个节点，中间跨过节点2

		//补充两个节点的情况，以及先交换节点1和节点2
        head = head->next;				  //返回的头结点
        head->next  = pred;				  //先把节点2转向到节点1
        pred->next = cur;				  //再把节点1跨过节点2，指向节点3
		
		//特殊情况补充完之后，开始循环
        while(cur != nullptr && cur->next != nullptr){	//因为操作cur和cur->next，所以避免访问空指针。
            ListNode* tmp = cur->next;					//记录cur下一位
            pred->next = tmp;
            cur->next = tmp->next;
            tmp->next = cur;							//此时交换完毕，整个过程保证有位置记录，不要断掉链表即可

            //更新位置
            pred = cur;
            cur = cur->next;
        }//while最后可以判断下cur指到末尾情况，同样符合逻辑。
        return head;	
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

尝试递归

递归的思想在上一篇学到，为了检验，把while内改成递归，尝试能否写出。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode* cur = head->next->next;
        ListNode* pred = head;

        head = head->next;//返回的头结点
        head->next  = pred;
        pred->next = cur;

        swap(pred,cur);
        return head;
    }

    void swap(ListNode* pred,ListNode* cur){
        if(cur == nullptr || cur->next ==nullptr ){//if判断也因为运行错误，调整。
            return;
        }
        ListNode* tmp = cur->next;
        pred->next = tmp;
        cur->next = tmp->next;
        tmp -> next = cur;
        swap(cur,cur->next);//第二个参数开始给成tmp，错误。对照while循环里更新位置给。
        return;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

代码随想录学习

学习内容

通过定义一个虚拟头节点，统一整个交换过程。

• cur指向dunmmy_node，操作交换1和2；
• cur指向交换之后的1，操作第二轮交换3和4；
• cur指向交换之后的3，操作第三轮交换5和6；
• 以此类推。
• 终止条件，n等于偶数时，cur->nextnullptr终止；n等于奇数时，cur->next->nextnulpptr终止。

新思路实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy_node = new ListNode(0,head);    //定义虚节点，并指向head
        ListNode* cur = dummy_node;

        //开始交换操作
        while(cur->next != nullptr && cur->next->next != nullptr){  //同时满足的关系。因为用到cur->next->next->next所以不能访问空指针
            ListNode* tmp = cur->next;
            ListNode* tmp1 = cur->next->next->next;

            cur->next = tmp->next;
            cur->next->next = tmp;
            tmp->next = tmp1;

            //更新位置,可以拉展链表看
            cur = cur->next->next;

        }
        head = dummy_node->next;
        delete dummy_node;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

ListNode* dummy_node = new ListNode(0,head); //创建节点，一开始没做好。少了new LIstNode。

---

总结

更简洁的代码：使用cur，确定用几个next来代替，如果不是很强，可以额外定义指针辅助判断；

如果操作前两个节点和后面的规律不统一，尝试加dummy_node，看可不可以统一操作。

（欢迎指正，转载标明出处）