給定 1->2->3->4, 你應該回傳 2->1->4->3
方法1：迭代
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next) return head;
ListNode* dummy = new ListNode(-1),*pre = dummy;
dummy->next = head;
while(pre->next && pre->next->next){
ListNode*t = pre->next->next;
pre->next->next = t->next;
t->next = pre->next;
pre->next = t;
pre = t->next;
}
return dummy->next;
}
};dummy是新鏈表的頭指標，該遍歷程序需要用到2個指標，pre和t，pre指向當前需要交換兩個節點的前一個節點，t指向需要交換兩個節點中后面的一個節點，每次交換完成之后對pre進行移動
方法2：遞回
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next) return head;
ListNode* first = head;
ListNode* second = head->next;
head = second;
first->next = swapPairs(second->next);
second->next = first;
return head;
}
};該程序用到了2個節點，fisrt指向需要交換的兩個節點中的前一個節點，second則指向后面的一個節點，每次把head賦值second，先隊員first->next賦值，再對second->next賦值，迭代的思想也是先對first進行操作，遞回需要額外的O(N)的堆疊空間
參考地址：https://blog.csdn.net/qq_34269988/article/details/89492526
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/155388.html
標籤：其他
上一篇：阿里P5-基礎知識