题目链接：Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,

Given {1,2,3,4}, reorder it to {1,4,2,3}.

这道题的要求是重新排列链表，要求不改变链表的值。

  1. 存储节点

先将每个节点存储到一个数组中，然后依次分别从前和后各取一个节点，直到相遇。不过这样，空间复杂度为O(n)。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution
{
public:
    void reorderList(ListNode *head)
    {
        if(head == NULL)
            return;
        
        vector<ListNode *> v;
        for(ListNode *p = head; p != NULL; p = p -> next)
            v.push_back(p);
        
        bool f = false;
        ListNode *p = head;
        for(int i = 0, j = v.size(); i < j; )
        {
            p -> next = f ? v[++ i] : v[-- j];
            p = p -> next;
            f = !f;
        }
        p -> next = NULL;
    }
};

  1. 递归处理

采用递归方式，从中间向两边处理，通过长度判断递归是否结束。递归时，传入左部分指针l和长度len，返回右部分指针r，然后每次把r后面节点放到l后面。

时间复杂度：O(n)

空间复杂度：O(1)

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

class Solution
{
public:
    void reorderList(ListNode *head)
    {
        int l = 0;
        for(ListNode *p = head; p != NULL; p = p -> next)
            ++ l;
        
        reorderList(head, l);
    }
private:
    ListNode * reorderList(ListNode *l, int len)
    {
        if(len == 0)
            return NULL;
        if(len == 1)
            return l;
        if(len == 2)
            return l -> next;
        
        ListNode *r = reorderList(l -> next, len - 2);
        ListNode * p = r -> next;
        r -> next = p -> next;
        p -> next = l -> next;
        l -> next = p;
        return r;
    }
};

  1. 中分反转合并

先通过快慢指针找到链表中间，分开，然后将右半部份反转，接着交错合并左右两个链表。

时间复杂度：O(n)

空间复杂度：O(1)

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

class Solution
{
public:
    void reorderList(ListNode *head)
    {
        if(head == NULL || head -> next == NULL)
            return;
        
        // 快慢指针找到中点
        ListNode *f = head -> next, *s = head;
        while(f != NULL && f -> next != NULL)
        {
            f = f -> next -> next;
            s = s -> next;
        }
        
        // 从中间分开
        ListNode *l = head, *r = s -> next;
        s -> next = NULL;
        
        // 反转右半部份
        ListNode *p = r -> next;
        r -> next = NULL;
        while(p != NULL)
        {
            ListNode *temp = p -> next;
            p -> next = r;
            r = p;
            p = temp;
        }
        
        // 交错合并两个链表
        while(l != NULL)
        {
            ListNode *temp = l -> next;
            l = l -> next = r;
            r = temp;
        }
    }
};