Swap Nodes in Pairs

    Example

    Given , you should return the list as 2->1->4->3.

    Challenge

    Your algorithm should use only constant space. You may not modify the values
    in the list, only nodes itself can be changed.

    1. 保存2.next
    2. 将2.next赋值为1
    3. 将1.next赋值为1中保存的2.next
    4. 将前一个链表节点的 next 指向1
    5. 更新前一个链表节点为1
    6. 更新当前的链表节点为1中保存的2.next

    链表类题目看似容易，但要做到 bug-free 其实不容易，建议结合图像辅助分析，onsite 时不要急，把过程先用伪代码写出来。然后将伪代码逐行转化。

    Java

    这里使用 dummy 处理不定头节点，首先将prev初始化为dummy, 然后按照题解中的几个步骤逐步转化，需要注意的是 while 循环中curr和都不能为null.

    复杂度分析

    在题解1 的分析过程中我们发现比较难处理的是 prev和下一个头的连接，要是能直接得到链表后面新的头节点该有多好啊。首先我们可以肯定的是若head == null || head.next == null时应直接返回，如果不是则求得交换奇偶节点后的下一个头节点并链接到之前的奇数个节点。这种思想使用递归实现起来非常优雅！

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) { val = x; }
    7.  * }
    8. public class Solution {
    10.      * @param head a ListNode
    11.      * @return a ListNode
    12.      */
    13.     public ListNode swapPairs(ListNode head) {
    14.         if (head == null || head.next == null) return head;
    16.         ListNode after = head.next;
    17.         head.next = swapPairs(after.next);
    18.         after.next = head;
    20.         return after;

    源码分析

    这个递归实现非常优雅，需要注意的是递归步的退出条件==>head == null || head.next == null).