【剑斩OFFER】算法的暴力美学——两两交换链表中的结点

一、题目描述

二、算法原理

思路：引入哨兵位 + 3 个指针

为什么要引入哨兵位？当我们实现完第一次交换时：

prev 的 next 要指向 cur ，所以引入哨兵位，这样一次循环就能搞定交换两两结点；这里我为什么要引入 nnext ？其实是为了方便对两个结点时的交换。

循环结束的条件：

当结点为偶数时：next == nullptr 就结束循环

当结点为奇数时：cur == nullptr 就结束循环

三、代码实现

/** * 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* prev = new ListNode(0,head); ListNode* cur = head,*next = head->next,*nnext = next->next,*ret = next; while(cur && next) { next->next = cur; cur->next = nnext; prev->next = next;//对交换后的结点进行连接 prev = cur;//开始更新 cur 、prev 、 next 、nnext cur = nnext; if(cur) next = cur->next; else break; if(next) nnext = next->next; } return ret; } };

探索性代码：

/** * 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) { ListNode* ret = nullptr; if(head == nullptr || head->next == nullptr) return head; else ret = head->next;//保存第一次交换的头结点 ListNode* prev = head; ListNode* cur = head->next; ListNode* tmpnode = nullptr; ListNode* swapnode = nullptr;//保存交换后的prev while(cur != nullptr)//使用临时变量来进行两两交换 { tmpnode = cur->next; cur->next = prev; prev->next = tmpnode; if(swapnode) swapnode->next = cur;//第二次，两两交换时，要把 prev 前一个结点链接上交换后的 cur swapnode = prev; prev = tmpnode; if(prev) cur = prev->next; else break; } return ret; } };