每日一题(LeetCode)----链表--两两交换链表中的节点

每日一题(LeetCode)----链表–两两交换链表中的节点

1.题目（[24. 两两交换链表中的节点](https://leetcode.cn/problems/spiral-matrix/)）

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

  示例 1：

  

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

  输入：head = []
  输出：[]
  示例 3：

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

  提示：

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

2.解题思路

思路一

先拆分成两个链表之后再进行合并

1.拆分

我们遍历一遍原链表，通过下标的奇偶拆分成两个链表

2.合并

(1)我们以通过下标为奇数得到的链表的表头作为新链表的表头，然后用两个指针变量交叉遍历两个链表（交叉遍历就是一个链表向后遍历了一个节点之后就换另一个链表向后遍历一个节点，这样循环，直到两个链表都遍历完成结束）

(2)将遍历到的节点放到新链表中即可(这里说是放到新链表中实际上只是改变了两个链表中的指针指向)

(3)最后我们返回这个新链表的表头

注意：如果给出的链表没有节点或者只有一个节点，我们不需要进行操作，直接返回原有链表即可

思路二：迭代法

1.我们创建一个虚拟头节点方便我们进行迭代操作，如下图

2.遍历链表实现两两交换

如果当前操作节点的下一个和当前操作节点的下一个的下一个的下一个同时不为空，进行下面操作

先保存一下当前操作节点的下一个节点和下一个的下一个节点为临时节点一和临时节点二

第一步：当前操作节点的下一个指向操作开始的节点的下一个的下一个， 第二步：当前操作节点的下一个的下一个指向临时节点一 第三步：当前操作节点的下一个的下一个的下一个指向临时节点二 第四步：下一次操作节点为当前操作节点的下一个的下一个，继续进行操作

看下图进行理解

思路三：递归法

递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

3.写出代码

思路一的代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //如果链表中没有元素，那么返回链表即可
        if(head==nullptr||head->next==nullptr){
            return head;
        }

        //拆成两个链表
        ListNode* head1=head;
        ListNode* head2=head->next;

        ListNode* Temp1=head1;
        ListNode* Temp2=head2;

        //进行拆分
        int flag=0;
        while(Temp1&&Temp2){
            if(flag%2==0){
                Temp1->next=Temp2->next;
                Temp1=Temp1->next;
                flag++;
            }
            else{
                Temp2->next=Temp1->next;
                Temp2=Temp2->next;
                flag++;
            }
           
        }

        Temp1=head1;
        Temp2=head2;
        flag=0;
        while(Temp1&&Temp2){
            if(flag%2==0){
                ListNode* delay2=Temp2->next;
                Temp2->next=Temp1;
                Temp2=delay2;
                flag++;
            }
            else{
                ListNode* delay1=Temp1->next;
                Temp1->next=Temp2;
                Temp1=delay1;
                flag++;
            }
        }
        return head2;
    }
};
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
40
41
42
43
44
45
46
47
48
49
50
51

思路二的代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyhead=new ListNode(0);
        dummyhead->next=head;
        ListNode* cur=dummyhead;
        while(cur->next!=nullptr&&cur->next->next!=nullptr){
            ListNode* temp1=cur->next;
            ListNode* temp2=cur->next->next->next;
            cur->next=cur->next->next;
            cur->next->next=temp1;
            cur->next->next->next=temp2;
            cur=cur->next->next;
        }
        return dummyhead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路三的代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
       if(head==nullptr||head->next==nullptr){
           return head;
       }
       ListNode* newHead=head->next;
       head->next=swapPairs(newHead->next);
       newHead->next=head;
       return newHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12