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.

解法：可以使用递归，每次交换前两个，将剩下的链表递归，返回的是新的链表头。

 

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode swapPairs(ListNode head) {14             if (head==null || head.next==null) {15                 return head;16             }17         ListNode p = head;18         ListNode begin=null;19            ListNode temp = p;20            21            p=p.next;22            temp.next=p.next;23            p.next=temp;24            if (begin==null) {25             begin = p;26         }27             p=p.next;28             p.next=swapPairs(p.next);29             return begin;30     }31 }