24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

方法一： 递归

1. 确定递归的参数
2. 终止条件
3. 调用单元的代码

每次递归都将问题的规模缩小，在题目中即缩小两个节点的长度，当缩小到没有节点或者只有一个节点时，直接返回该节点的值，因为没办法交换，返回值给上一层中两个节点的第一节点的next值。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head; //终止条件
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }
}

方法二：迭代法
每次交换两个节点，思考终止条件
首先设置一个哑结点dummyHead = new ListNode(0); ListNode prev, cur, next
一开始

0->1->2->3->4 ， prev  = 0, cur = 1, next = 2

交换

prev.next =  cur;
cur.next = next.next;
next.next = cur;

一次迭代后

0->2->1->3->4, prev = 0, cur = 1, next = 2

更新 prev, cur, next

prev = cur;
cur  = next.next;
next = cur.next;

继续后面的迭代


终止条件：

1. 奇数个节点（只剩一个节点未交换也不用交换）， next = null
2. 偶数个节点（一个节点不剩）， cur = null

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        ListNode prev = dummyHead, cur = head;
        prev.next = head;
        while(cur != null){
            ListNode next = cur.next;
            if(next == null) break; //只剩一个节点不需要交换
            prev.next = next;
            cur.next = next.next;
            next.next = cur;
            prev = cur;
            cur = cur.next;
        }
        return dummyHead.next;
    }
}