題目描述
給定一個鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)（結(jié)點(diǎn)進(jìn)行交換而不是簡單地進(jìn)行值交換），并返回交換后的鏈表栈源。
示例：
輸入：1->2->3->4
輸出：2->1->4->3
解析
實現(xiàn)技巧：遞歸實現(xiàn)
實現(xiàn)方法
如果利用調(diào)整指針的方式完成鏈表的交換會產(chǎn)生大量的指針交換操作，難度較大衫樊。
這里介紹遞歸實現(xiàn)：
- 鏈表每次交換前兩個結(jié)點(diǎn)
- 后面n-2個結(jié)點(diǎn)作為新的鏈表遞歸實現(xiàn)
- n-2結(jié)點(diǎn)的結(jié)果放到前兩個結(jié)點(diǎn)的鏈表后面
遞歸實現(xiàn)代碼
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){//遞歸判斷條件了罪，如果無結(jié)點(diǎn)或者只有一個結(jié)點(diǎn)直接返回
return head;
}
/*取出前兩個結(jié)點(diǎn)*/
ListNode first = head;
ListNode second = head.next;
/*head指向新的鏈表*/
head = second.next;
/*前兩個結(jié)點(diǎn)交換位置*/
second.next = first;
/*head鏈表的結(jié)果鏈接到前兩個結(jié)點(diǎn)鏈表后面*/
first.next = swapPairs(head);
/*返回結(jié)果*/
return second;
}
