题目描述
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表
注:不能单纯改变节点内部的值,而是需要实际的进行节点交换
示例:
输入:1->2->3->4->8
输出:2->1->4->3->8
三指针法
在正式开始交换之前,先排除链表为空或者链表只有1个节点的情况(节省空间)
定义一个先头节点p,让它的next指向head
初始化指针pre指向p
设定标志位isHead(用于更新head)
在每一轮循环中:
1、初始化
初始化临时指针a为 pre->next
初始化临时指针b为 a->next
(从左到右分别是 pre、a、b,a和b指向将要交换的节点)
2、交换
操作a、b、pre指针
3、判断是否需要更新head
4、更新pre
当pre->next或者(pre->next)->next为空时,表示交换工作结束
代码如下:
/**
* 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==NULL || head->next==NULL){
return head;
}
ListNode p(0,head);
bool isHead = true;
ListNode *pre=&p;
while(pre->next!=NULL && (pre->next)->next!=NULL){
ListNode *a=pre->next;
ListNode *b=a->next;
a->next=b->next;
b->next=a;
pre->next=b;
if(isHead==true){
head=b;
isHead=false;
}
pre=a;
}
return head;
}
};