題目描述
給定一個鏈表，兩兩交換其中相鄰的節點，并返回交換后的鏈表。

你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。

示例:

給定 1->2->3->4, 你應該返回 2->1->4->3.

方法一（遞歸）：
將配對交換過程拆解為多個以兩個元素為一對的子問題
…n(k-1) -> n(k)->n(k+1)->…
假如n(k+1)之后已經完成逆置，此時置換之后…->n(k-1)->n(k+1)->n(k)->…

Node *p = head -> next;
head -> next = p -> next;
p -> next = head;

實現如下:

ListNode* swapPairs(ListNode* head) {if(head == NULL || head -> next == NULL) {return head;}ListNode *p = head -> next;head -> next = swapPairs(p -> next);p -> next = head;return p;
}

方法二（非遞歸）：

構造一個虛擬的頭節點，同時當前鏈表遍歷的結束條件：
如果鏈表長度為偶數，那么p->next->next = NULL
如果鏈表長度為奇數，那么p->next = NULL

p代表當前節點的上一個節點，next代表置換兩個之后的下一個節點。

同時兩兩交換之后的相互指向形態為：
node2 -> next = node1;
node1 -> next = next;
p -> next = node2;

p = node1;

ListNode* swapPairs(ListNode* head) {ListNode * dummHead = new ListNode(0);dummHead->next = head;ListNode *p = dummHead;while(p->next && p->next->next){ListNode * node1 = p->next;ListNode * node2 = node1->next;ListNode * next = node2->next;node2->next = node1;node1->next = next;p->next = node2;p = node1;}return dummHead->next;      
}

總結

以上是生活随笔為你收集整理的leetcode-24 两两交换链表中的节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。