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

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

双指针解法：

时间复杂度：O(n)
空间复杂度：O(2n)

    class Solution {
        public ListNode swapPairs(ListNode head) {
            // - 迭代解法
            if (null == head || null == head.next) {
                return head;
            }

            // - 初始化一个虚拟头节点
            ListNode dummy = new ListNode(0, head);
            ListNode currentNode = dummy;

            // - 循环链表 两个节点速度
            while (null != currentNode.next && null != currentNode.next.next){
                ListNode node1 = currentNode.next;
                ListNode node2 = currentNode.next.next;
                // - 此处转换很有趣 需要多敲几遍
                currentNode.next = node2;
                node1.next = node2.next;
                node2.next = node1;
                currentNode = node1;
            }
            return dummy.next;
        }
    }

递归解法：

时间复杂度：O(n)
空间复杂度：O(n^2)

    class Solution {
        public ListNode swapPairs(ListNode head) {
            // - 递归解法
            if (null == head || null == head.next) {
                return head;
            }

            // - 下一个节点
            ListNode next = head.next;
            // - 每次递归走两步
            head.next = swapPairs(head.next.next);
            // - 反转
            next.next = head;
            return next;
        }
    }