24. 兩兩交換鏈表中的節點
這道題乍一看，這有啥難度 就是把反轉鏈表變成兩個兩個反轉
思路沒有錯的 解決的問題分別是：
1 如何反轉鏈表
2 如何按照指定長度反轉鏈表
我們一個一個來看，首先是如何反轉鏈表，絕大多數人首先想到的一定是使用一個前置指標prev進行反轉，例如下面所示：
ListNode * reverseListNode(ListNode * head){
if(head == nullptr) return nullptr;
if(head->next == nullptr) return head;
ListNode * prevNode = nullptr;
ListNode * currentNode = head;
while(currentNode!=nullptr){
ListNode * tmpNode = currentNode->next;
currentNode->next = prevNode;
prevNode = currentNode;
currentNode = tmpNode;
}
return prevNode;
}之后是何如K個一組反轉鏈表呢？同leetcode25題，
首先也需要有一個反轉鏈表的函式，我們對上面的函式做一個小小改動添加一個lastNode的引數
//反轉位置是head到last-1的鏈表
ListNode * reverseListNode(ListNode * head, ListNode * last){
if(head == nullptr) return nullptr;
if(head->next == nullptr) return head;
ListNode * currentNode = head;
ListNode * prevNode = nullptr;
while(currentNode != last){
auto tmpNode = currentNode->next;
currentNode->next = prevNode;
prevNode = currentNode;
currentNode = tmpNode;
}
return prevNode;
}
ListNode * reverseGroup(ListNode * head, int k){
ListNode * last = head;
//注意這里實際上last已經移動到了[k]
for(auto i = 0; i < k; i++){
if(last != nullptr){
last = last->next;
}else{
return head;
}
}
auto lastNode = reverse(head, last);
head->next = reverseGroup(last, k);
return lastNode;
}其實這里還有一個問題，如果鏈表中最后一組不滿k個數，可以分為兩種輸出結果，一種是繼續反轉剩余不滿k個的那組，一個是剩余不滿的那組不反轉，這里題目中是不反轉，如果改為需要反轉，可以直接修改為：
for(auto i = 0; i < k; i++){
if(last != nullptr){
last = last->next;
}else{
return head;
}
}
=======================================
for(auto i = 0; i < k; i++){
if(last != nullptr){
last = last->next;
}else{
//注意修改這里
return reverse(head,last);
}
}這是面試官最喜歡問的一個變種，
回到最初的問題，兩個兩個交換是不是就是直接把k設定為2.
當然這里有一個更簡單的解法，利用遞回的方式：
ListNode* swapPairs(ListNode* head) {
if(head == nullptr) return nullptr;
if(head->next == nullptr) return head;
ListNode* newhead = head->next;
//這里遞回
head->next = swapPairs(newhead->next);
newhead->next = head;
return newhead;
}這種遞回的方式是不是會有堆疊溢位的風險呢？
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/252571.html
標籤：python
上一篇：程式編譯
下一篇：Lambda運算式