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

链接

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. 合并两个链表为一个

实现

这个题目综合了链表的好几个操作：链表逆序、链表拆分、链表合并、链表遍历。

考虑到节点数目未知，所以不应该考虑使用栈等消耗空间的方式。

#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]);
}