两两交换链表中的节点
自己写
原理为两个交换，交换参数为pre和cur。
交换成功后，连接pre的前一个pre2和cur的后一个aft。
#include <iostream> #include <vector> #include<algorithm> using namespace std; 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* pre, * cur, *temp ,*aft,*pre2,*head_test; //链表长度为0或者为1 if (head == nullptr || head->next == nullptr)return head; ListNode test(0,nullptr); head_test = head->next; pre = head; pre2 = &test; cur = pre->next; //链表长度大于2以上 while (cur) { aft = cur->next; if (pre != nullptr|| cur != nullptr) { temp = cur->next; cur->next = pre; pre->next = temp; pre2->next = cur; } else break; pre2 = pre; pre = aft; if (pre != nullptr)cur = pre->next; else break; } return head_test; } }; int main() { vector<int> head = { 1,2}; ListNode* head_test = new ListNode(0); ListNode* test , *cur = head_test; Solution a; for (int i = 0; i < head.size(); i++) { ListNode* temp = new ListNode(head[i]); cur->next = temp; cur = cur->next; } cur->next = nullptr; cur = head_test; cout << "cur list" << endl; while (cur->next != nullptr) { cout << cur->val << ' '; cur = cur->next; } cout << cur->val << endl; test = a.swapPairs(head_test->next); while (test->next != nullptr) { cout << test->val << ' '; test = test->next; } cout << test->val << ' '; return 0; }
卡尔
class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点 dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作 ListNode* cur = dummyHead; while (cur->next != nullptr && cur->next->next != nullptr) { ListNode* tmp = cur->next; // 记录临时节点 ListNode* tmp1 = cur->next->next->next; // 记录临时节点 cur->next = cur->next->next; // 步骤一 cur->next->next = tmp; // 步骤二 cur->next->next->next = tmp1; // 步骤三 cur = cur->next->next; // cur移动两位，准备下一轮交换 } return dummyHead->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==nullptr || head->next==nullptr) return head; ListNode *result = head->next; ListNode *pre = new ListNode(0,head) ; ListNode *cur1 = head; ListNode *cur2 ; ListNode *cur_next ; while(cur1 != nullptr && cur1->next != nullptr) { cur2 = cur1->next; cur_next = cur2->next; pre->next = cur2; cur2->next = cur1; cur1->next = cur_next; pre = cur1; cur1 = cur_next; } return result; } };
