两两交换链表中的结点(迭代法、递归法)_head->next = node1; node1->next = node2; node2->ne
赞
踩
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
迭代法解题思路：
建立一个头结点和一个指向头结点的指针temp，再交换该指针的后两个结点Node1和Node2。交换之前temp->Node1->Node2，
交换之后temp->Node2->Node1，之后令temp=Node1，继续对temp之后的两个结点交换，循环到Node为空或者Node为空。
// 无注释版：
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* dummyHead=new ListNode(0);
dummyHead->next=head;
ListNode* temp=dummyHead;
while(temp->next!=NULL&&
temp->next->next!=NULL) {
ListNode* Node1=temp->next;
ListNode* Node2=temp->next->next;
temp->next=Node2;
Node1->next=Node2->next;
Node2->next=Node1;
temp=Node1;
}
return dummyHead->next;
}
};
// 注释版：
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: // 传入给定链表head
ListNode* swapPairs(ListNode* head) {
// 创建头结点和指向头结点的指针
// 并让头结点指向head的第一结点
ListNode* dummyHead=new ListNode(0);
dummyHead->next=head;
ListNode* temp=dummyHead;
// 实现交换的循环
while(temp->next!=NULL&&
temp->next->next!=NULL) {
// 实现Node1和Node2的交换
ListNode* Node1=temp->next;
ListNode* Node2=temp->next->next;
temp->next=Node2;
Node1->next=Node2->next;
Node2->next=Node1;
// 让temp指向交换后的Node1，继续下一循环
temp=Node1;
}
// 返回交换后的链表的第一结点
return dummyHead->next;
}
};
递归法解题思路：
进行两两交换的递归的终止条件：链表只有一个或没有结点，无法交换。
把每两个结点看作一个子链表
用head表示原始链表的第一个结点(交换后的第二个结点)，用newhead表示原始链表的第二结点(交换后的第一结点)。
令head.next =
swapPairs(newHead.next)，表示将其余节点进行两两交换，然后返回交换后的链表的第一个结点接到head的后一位。
最后newhead.next = head，让第二结点指向第一结点
// 无注释版
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==NULL||head->next==NULL)
return head;
ListNode* newhead=head->next;
head->next=
swapPairs(newhead->next);
newhead->next=head;
return newhead;
}
};
// 注释版
// 链表的定义
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==NULL||head->next==NULL)
return head;
// 让newhead指向原始链表第二结点
ListNode* newhead=head->next;
// 把交换后的链表接到head后面
head->next=
swapPairs(newhead->next);
// 让原始链表第二结点指向原始链表第一结点
newhead->next=head;
// 返回交换后的链表第一结点
return newhead;
}
};
递归的执行步骤：
让newhead指向原始链表第二结点，然后进入下一子链表继续让newhead指向子链表的第二结点，到终止条件后，返回(空或一个结点)接到最后一个子链表的第一结点的后面，然后让该子链表的第二结点指向第一结点(完成交换)，然后把交换后的该链表的第一结点返回倒数第二子链表的第一结点，然后让该子链表的第二结点指向第一结点，之后继续返回上一子链表，直到返回第一个子链表继续完成第一个子链表的交换(整个链表完成两两交换)。
