LeetCode刷题|recording:24. 两两交换链表中的节点 c++|算法|链表|数据结构

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

文章图片

解法思想：一步一步迭代去解，模拟整个交换过程，为了方便操作，我们需要定义一个虚拟指针指向头结点前面，并定义一个临时指针指向虚拟结点，操作指针进行后续操作，还需要两个临时变量指向需要交换的结点
如下图：

文章图片

文章图片

class Solution { public: ListNode* swapPairs(ListNode* head) { //创建虚拟头结点 ListNode *newhead=new ListNode(0); newhead->next=head; ListNode *cur=newhead; while(cur->next!=nullptr&&cur->next->next!=nullptr) { ListNode *tmp=cur->next; ListNode *tmp1=cur->next->next; cur->next=tmp1; tmp->next=tmp1->next; tmp1->next=tmp; cur=cur->next->next; } return newhead->next; } };

对于这种需要交换，反转的题目来说，利用栈的先进后出的能力也是可以的。
我们利用一个 stack，然后不断迭代链表，每次取出两个节点放入 stack 中，再从 stack 中拿出两个节点。
借助 stack 后进先出的特点，放进去的时候是 1,2 。拿出来的时候就是 2，1 两个节点了。
再把这两个节点串联起来，重复这个逻辑遍历完整个链表，就可以做到两两反转的效果了。
虽然用到了 stack，但因为只存了两个元素，所以空间复杂度还是 O(1)，时间复杂度是 O(n)。

class Solution { public: ListNode* swapPairs(ListNode* head) {stack sc; //创建一个栈用来进栈出栈交换两两结点 ListNode * dummyHead =new ListNode(0); //虚拟结点ListNode * pre=dummyHead; while(head!=nullptr&&head->next!=nullptr) { //入栈两个结点 sc.push(head); sc.push(head->next); //结点指针指向下一组开头 head=head->next->next; //出栈 pre->next=sc.top(); //将栈头的节点，也就是压入的第二个节点加入链表 pre=pre->next; sc.pop(); pre->next=sc.top(); pre=pre->next; sc.pop(); } pre->next=head; return dummyHead->next; } };

另一种写法：

public: ListNode* swapPairs(ListNode* head) { if(!head) return nullptr; stack s; ListNode* node=new ListNode(); ListNode* dummy=node; while(head!=nullptr){ s.push(head); head=head->next; if(s.size()==2){ //一旦栈中元素有2个，就把元素接在node后面 while(!s.empty()){ node->next=s.top(); node=node->next; s.pop(); } } } if(s.size()==1){ //节点数为奇数的情况下，最终栈中还剩下最后一个元素，接在node最后 node->next=s.top(); node=node->next; } node->next=nullptr; return dummy->next; } };

【LeetCode刷题|recording:24. 两两交换链表中的节点】