Given a linked list, swap every two adjacent nodes and return its head.
For example,Given 1->2->3->4,
you should return the list as 2->1->4->3
.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
本題的大意就是交換鏈表中相鄰的結(jié)點(diǎn)忽你，限定常數(shù)的空間復(fù)雜度
解析：
因?yàn)槭莾蓛山粨Q結(jié)點(diǎn)，因此我們可以將“一個(gè)很長(zhǎng)的鏈表進(jìn)行兩兩反轉(zhuǎn)結(jié)點(diǎn)”這個(gè)大問題分解成一個(gè)個(gè)像“反轉(zhuǎn)只有兩個(gè)結(jié)點(diǎn)or更少”這樣的子問題拨与，又因?yàn)槊總€(gè)子問題都是相同的哩治，因此我們可以采用分支策略（遞歸）
-
算法描述：
Paste_Image.png 注意事項(xiàng)：
遞歸一定要注意遞歸出口秃踩，注意棧溢出
代碼：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null)
return null;
if(head.next == null)
return head;
ListNode temp = head.next;
head.next = swapPairs(temp.next);
temp.next = head;
return temp;
}
}
