leetcode 24-两两交换链表中的节点

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
说明:
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换

解析

解读：如上图所示，需要交换1，2两个节点。那么分三步走：

• 第一步：修改pre节点的next指向节点2
• 第二步：修改节点1的next指向节点3
• 第三步：修改节点2的next指向节点1
  然后只需要保存上一次交换后的末尾节点，一直循环，考虑好边界条件。

代码实现

public static ListNode swapPairs(ListNode node) {


        if(node == null || node.next == null){
            return node;
        }
        /**
         * 因为头节点是start而不是pre，所以需要新建一个虚拟节点root
         */
        ListNode root = new ListNode(0);
        root.next = node;
        ListNode pre = root;
        while (pre.next != null && pre.next.next != null){
            /**
             * 定义start和then
             */
            ListNode start = pre.next;
            ListNode then = pre.next.next;
            /**
             * 三步走
             */
            pre.next = then;
            start.next = then.next;
            then.next = start;
            /**
             * 下一个pre节点为start节点
             */
            pre = start;
        }

        /**
         * 这里应该也是返回虚拟节点的next
         */
        return root.next;
    }