[LeetCode] 143. Reorder List 重新排序链表

陪她去流浪 桃子 2018年05月20日 编辑 阅读次数：1983

链接

143. Reorder List - LeetCode

题意

给定一个单链表：$L_0 → L_1 → ... → L_{n-1} → L_n$,
将它重新排序为：$L_0 → L_n → L_1 → L_{n-1} → L_2 → L_{n-2} → ...$

要求

  • 不能修改节点值域，只能修改节点的指向

举例

  • 1→2→3→4 重新排序为 1→4→2→3
  • 1→2→3→4→5 重新排序为 1→5→2→4→3

分析

从题意即举例可以看出，大概完成了以下几步操作：

  1. 把原链表从中间分成两部分
  2. 把第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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include <stdio.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newRoot = NULL;
    while(head != NULL) {
        struct ListNode* next = head->next;
        head->next = newRoot;
        newRoot = head;
        head = next;
    }
    return newRoot;
}

void splitList(struct ListNode* head, struct ListNode** l1, struct ListNode** l2) {
    int n = 0;
    int m;
    struct ListNode* p = head;
    while(p != NULL) {
        n++;
        p = p->next;
    }
    m = n / 2 - 1;
    p = head;
    while(m--) {
        p = p->next;
    }
    *l2 = p->next;
    p->next = NULL;
    *l1 = head;
}

struct ListNode* mergeList(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode h;
    struct ListNode* p = &h;
    while(l1 != NULL && l2 != NULL) {
        p->next = l1;
        l1 = l1->next;
        p->next->next = l2;
        l2 = l2->next;
        p = p->next->next;
    }
    for(l1 = l1 != NULL ? l1 : l2; l1 != NULL; l1 = l1->next) {
        p->next = l1;
        p = p->next;
    }
    p->next = NULL;
    return h.next;
}

void print(struct ListNode* n) {
    for(struct ListNode* p = n; p != NULL; p = p->next) {
        printf("%d ", p->val);
    }
    printf("\n");
}

void reorderList(struct ListNode* head) {
    if(head == NULL || head->next == NULL || head->next->next == NULL) {
        return;
    }
    struct ListNode *l1, *l2;
    splitList(head, &l1, &l2);
    print(l1);
    l2 = reverseList(l2);
    print(l2);
    (void)mergeList(l1, l2);
    print(head);
}

int main() {
    const int n = 5;
    struct ListNode nodes[n];
    for(int i = 0; i < n; i++) {
        nodes[i].val = i + 1;
        nodes[i].next = &nodes[i+1]; // i+1 can equal to n
    }
    nodes[n-1].next = NULL;
    reorderList(&nodes[0]);
}

标签：链表 · LeetCode · 数据结构

相关文章