LeetCode 24：Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

Example:

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

Note:

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

传入一个链表，要求返回一个链表，每两个节点进行交换位置，要求额外空间恒定，不能修改节点的值，只能修改节点本身，那就是不停更新指针引用

难度是Medium，但是感觉挺难，参考了下提交的Solution；最后阿里云博客上还有一种C++实现的递归的方法，照搬成Java提交了下也是OK的，已写明转载链接

画了下简易图

（1）创建一个头节点，first不动，first.next作为交换后的头指针，最终返回；start指向每次循环交换两个节点中第一个节点

源码

ListNode first = new ListNode(0);
first.next = head;
ListNode prev = first;
ListNode start = head;

初始状态图下，需要关注几个指针的位置，后面的状态（比如1和2处理完了，到3和4了）也要变成对应引用方式，草图

（2）start指针引用每次引用交换前两个节点中前面一个节点，记录下次的起点，所以每次交换的时候，先移到下两个节点起点

源码

start = head.next.next;

草图

（3）交换位置，先将后面一个节点指向前面一个节点，后面断了也没关系，反正start已经记录了下一轮回

源码

head.next.next = head;

草图

（4）将头节点换个位置，因为要交换位置，比如最终是0->2->1，因此更换prev.next的引用，同时也修改了first.next指向的位置，这才是最终要返回的

源码

prev.next = head.next;

草图

（5）其实上面first.next已经指向了0->2->1，剩下的工作就是要恢复成（1）的指针的状态，也就是保持34和12时候一样；首先1作为34的头结点（因为1交换后在后方），就像0作为12的头结点一样，因此1指向3

源码

head.next = start;

草图

（6）prev指向头结点，此时是1所在节点

源码

prev = head;

草图

（7）初始情况，head和start指向同一个节点，此时都是3

源码

head = head.next;

草图

这样就折腾完了，可以对比（1）的初始图，此时的1所在的节点相当于初始0所在的节点一样，这样就可以进入下一个循环

挺麻烦的，Java源码

package com.maoxiaomeng;


/**
 * Copyright (C), 2014-2018, maoxiaomeng.com
 * FileName: Solution
 * Author:   lihui
 * Date:     2018/4/14 00:37
 */


class ListNode { 
    int val;
    ListNode next;
    ListNode(int x) { 
        val = x; 
    }
}
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode first = new ListNode(0);
        first.next = head;
        ListNode prev = first;
        ListNode start = head;
        while (head != null && head.next != null) {
            start = head.next.next;
            head.next.next = head;
            prev.next = head.next;
            head.next = start;
            prev = head;
            head = head.next;
        }
        
        return first.next;
    }
}

还有人给出了更简洁的递归解决方法

最近递归弄得头大，只能凭感觉想通了

来自链接：https://yq.aliyun.com/articles/870

Java源码

package com.maoxiaomeng;


/**
 * Copyright (C), 2014-2018, maoxiaomeng.com
 * FileName: Solution
 * Author:   lihui
 * Date:     2018/4/14 00:37
 */


class ListNode { 
    int val;
    ListNode next;
    ListNode(int x) { 
        val = x; 
    }
}
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode first = head.next;
        head.next = swapPairs(first.next);
        first.next = head;
        return first;
    }
}

OVER