LeetCode24—两两交换链表中的节点

老规矩，先贴个人代码（看了标准答案的代码总觉得自己的代码…不可描述)

/**
 * 两两交换链表中的节点
 */
public class Leetcode_24 {

    public ListNode swapPairs(ListNode head) {
        if(head == null) return null;
        ListNode pre = new ListNode(-1);
        ListNode node1 = pre;
        pre.next = head;
        ListNode node2 = head;
        ListNode node3 = head.next;
        while(node1!=null&&node2!=null&&node3!=null){
            node2.next = node3.next;
            node3.next = node2;
            node1.next = node3;
            node1 = node1.next.next;
            node2 = node2.next;
            if(node3.next.next==null){
                break;
            }
            else {
                node3 = node3.next.next.next;
            }
        }
        return pre.next;
    }
    public static void main(String[] args) {
        Leetcode_24 leetcode_24 = new Leetcode_24();
        ListNode node0 = null;
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);
        // node1.next = node2;
        // node2.next = node3;
        // node3.next = node4;
        // node4.next = node5;
        // node5.next = node6;
        // node6.next = node7;
        // // node7.next = node8;
        ListNode node = leetcode_24.swapPairs(node0);
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println("");
    }
}

本题我使用的是迭代的方法，首先是创建一个头节点，它的下一个节点用来存储生成新链表的头节点，同时，因为要交换两个节点，所以肯定需要一个节点来存储交换节点前面节点的前驱节点。

比如要交换节点1和2.我们就可以假象前面有一个节点0，这个节点0就是1的前驱节点，可以让这三个节点同时向后移动两个单位，再次进行节点交换，直到节点1为空或者节点2为空为止。

从解法上看，只需要遍历一次链表既可以完成数据交换，所以算法的时间复杂度为O(1)。

官方解法

迭代的思路和我一致，这里不再赘述。

递归解法

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

先贴上图示：

递归的解法：首先第一步让前节点指向两个交换节点的后一个节点，这是递，然后第二步，让被交换的第二个节点指向交换的第一个节点，这是归，从这一思想我们可以总结出，返回值就是next，而且已经是被处理好的（交换好的）。

这个递归解法就我个人而言还是挺难想到的，还是缺少练习，继续努力！