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

非递归方法（自己写的）

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null)
            return head;
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            ListNode curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = cur;
            pre.next = curNext;
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}

递归方法（看别人的）

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;
    }
}

递归思路

1. 找终止条件

当递归到链表为空或链表中只剩一个元素时。没有可以交换的节点，就终止递归

2.找返回值

返回给上一层的值应该是已经交换完成之后的子链表

3.单次的过程

因为递归时重复做一样的事，从宏观上讲，只考虑某一部是怎么完成的。
假设待交换的两个节点分别是head和next，next应该接受上一级返回的子链表。
就相当于是一个含有三个节点的链表交换前两个节点。