Leetcode(143) Reorder List

发表于 | 分类于

Description

Given a singly linked list L: L0→L1→…→L**n-1→Ln,
reorder it to: L0→L**n→L1→L**n-1→L2→L**n-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

1
Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

1
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

解法

思路：

  1. 找到链表的中点，并将链表从中点处断开，形成两个独立的链表

  2. 将第二个链翻转。

  3. 将第二个链表的元素间隔地插入第一个链表中。

具体代码如下：

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
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        int length = 0;
        ListNode start = head;
        while (start != null) {
            length++;
            start = start.next;
        }
        ListNode head2 = head;
        ListNode pre = null;
        int move = length / 2;
        while (move > 0) {
            pre = head2;
            head2 = head2.next;
            move--;
        }
        pre.next = null;
        head2 = reverseList(head2);
        ListNode newhead = head;
        ListNode head1 = head.next;
        newhead.next = null;
        int step = 1;
        while (head1 != null || head2 != null) {
            if (step % 2 == 1) {
                if (head2 != null) {
                    newhead.next = head2;
                    newhead = newhead.next;
                    head2 = head2.next;
                    newhead.next = null;
                }
                step++;
            } else {
                if (head1 != null) {
                    newhead.next = head1;
                    newhead = newhead.next;
                    head1 = head1.next;
                    newhead.next = null;
                }
                step++;
            }
        }
        newhead.next = null;

    }

    ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        if (head.next == null) {
            return head;
        }
        ListNode res = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }
}