LeetCode-143. 重排链表-Java-medium

题目链接

法一（快）

    /**
     * 快慢指针找到中间节点
     *
     * @param head
     * @return
     */
    private ListNode findMiddleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 反转后半段链表
     *
     * @param afterHead
     * @return
     */
    private ListNode reverseList(ListNode afterHead) {
        ListNode pre = null, cur = afterHead, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 交叉合并前半段链表和后半段链表
     *
     * @param frontHead
     * @param afterHead
     */
    private void mergeList(ListNode frontHead, ListNode afterHead) {
        ListNode frontNext, afterNext;
        while (frontHead != null && afterHead != null) {
            frontNext = frontHead.next;
            afterNext = afterHead.next;
            frontHead.next = afterHead;
            frontHead = frontNext;
            afterHead.next = frontHead;
            afterHead = afterNext;
        }
    }

    /**
     * 法一（快）
     * （1）快慢指针找到中间节点
     * （2）反转后半段链表
     * （3）交叉合并前半段链表和后半段链表
     *
     * @param head
     */
    public void reorderList_1(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode mid = findMiddleNode(head);
        ListNode frontHead = head, afterHead = mid.next;
        mid.next = null; // 中断前半部分链表和后半部分链表
        afterHead = reverseList(afterHead);
        mergeList(frontHead, afterHead);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

法二（双端队列）

    /**
     * 法二（双端队列）
     *
     * @param head
     */
    public void reorderList_2(ListNode head) {
        Deque<ListNode> deque = new LinkedList<>();
        ListNode cur = head;
        while (cur != null) {
            deque.addLast(cur);
            cur = cur.next;
        }
        while (!deque.isEmpty()) {
            if (cur == null) {
                cur = deque.pollFirst();
            } else {
                cur.next = deque.pollFirst();
                cur = cur.next;
            }
            cur.next = deque.pollLast();
            cur = cur.next;
        }
        if (cur != null) {
            cur.next = null;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

本地测试

        /**
         * 143. 重排链表
         */
        lay.showTitle(143);
        Solution143 sol143 = new Solution143();
        int[] nums143 = new int[]{1, 2, 3, 4, 5};
        ListNode head143 = new ListNode();
        head143 = listOpt.creatListByArray(head143, nums143);
        listOpt.showList(head143);
        sol143.reorderList_1(head143.next);
        listOpt.showList(head143);
        sol143.reorderList_2(head143.next);
        listOpt.showList(head143);
1
2
3
4
5
6
7
8
9
10
11
12
13