24. Swap Nodes in Pairs

题目：

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.

链接：https://leetcode.com/problems/swap-nodes-in-pairs/#/description

4/12/2017

4ms, 85%

链表题画画图比较好

 1 public class Solution {
 2     public ListNode swapPairs(ListNode head) {
 3         if (head == null || head.next == null) return head;
 4         ListNode dummy = new ListNode(-1);
 5         dummy.next = head;
 6         ListNode prev = dummy;
 7         ListNode cur = head;
 8 
 9         while(cur != null && cur.next != null) {
10             prev.next = cur.next;
11             cur.next = cur.next.next;
12             prev.next.next = cur;
13             prev = cur;
14             cur = cur.next;
15         }
16         return dummy.next;
17     }
18 }

别人的recursive做法，虽然空间复杂度高，但是这种思路挺有意思，贴出来的代码比较容易懂一点

https://discuss.leetcode.com/topic/4351/my-accepted-java-code-used-recursion

https://discuss.leetcode.com/topic/41459/java-simple-recursive-solution

 1 public class Solution {
 2     public ListNode swapPairs(ListNode head) {
 3         if (head == null || head.next == null) return head;
 4         ListNode second = head.next;
 5         ListNode third = second.next;
 6         
 7         second.next = head;
 8         head.next = swapPairs(third);
 9         
10         return second;
11     }
12 }