题目描述

题目链接：143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

1	L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

1	L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例1：

1 2	输入：head = [1,2,3,4] 输出：[1,4,2,3]

示例2：

1 2	输入：head = [1,2,3,4,5] 输出：[1,5,2,4,3]

提示：

链表的长度范围为 [1, 5 * 10(4)]
1 <= node.val <= 1000

我的题解

方法一：双端队列

思路

很明显的思路，先遍历一遍，放入双端队列中，然后从两边取节点重组链表。

代码

class Solution {
    public void reorderList(ListNode head) {
        ArrayDeque<ListNode> queue = new ArrayDeque<>();
        ListNode p = head;
        while (p != null) {
            queue.offer(p);
            p = p.next;
        }
        ListNode h = queue.pollFirst();
        boolean f = true;
        while (!queue.isEmpty()) {
            h.next = f ? queue.pollLast() : queue.pollFirst();
            f = !f;
            h = h.next;
        }
        h.next = null;
    }
}

结果

执行用时：3 ms, 在所有 Java 提交中击败了32.51%的用户

内存消耗：44 MB, 在所有 Java 提交中击败了71.11%的用户

方法二：查找中间节点+链表反转+合并链表

思路

首先查找链表的中间节点，然后将第二部分链表反转，最后再合并两部分的链表，可以达到O(1)的空间复杂度。

代码

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode center = findCenterNode(head);
        ListNode l1 = head;
        ListNode l2 = reverseList(center);
        mergeList(l1, l2);
    }

    private void mergeList(ListNode l1, ListNode l2) {
        ListNode h = new ListNode(-1);
        boolean f = true;
        while (l1 != null && l2 != null) {
            if (f) {
                h.next = l1;
                l1 = l1.next;
            } else {
                h.next = l2;
                l2 = l2.next;
            }
            f = !f;
            h = h.next;
        }
        h.next = l1 != null ? l1 : l2;
    }

    private ListNode reverseList(ListNode head) {
        ListNode p1 = null, p2 = head;
        while (p2 != null) {
            ListNode t = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = t;
        }
        return p1;
    }

    private ListNode findCenterNode(ListNode head) {
        ListNode p1 = head, p2 = head, t = head;
        while (p2 != null && p2.next != null) {
            t = p1;
            p1 = p1.next;
            p2 = p2.next.next;
        }
        t.next = null;
        return p1;
    }
}