单链表分割算法：C++实现及优化

#include <stdio.h> #include <stdlib.h>

typedef int ElemType; typedef struct ListNode { ElemType data; struct ListNode *next; } ListNode, *LinkList;

LinkList createList() { LinkList head = (LinkList) malloc(sizeof(ListNode)); head->next = NULL; return head; }

void insert(LinkList list, ElemType x) { ListNode node = (ListNode) malloc(sizeof(ListNode)); node->data = x; node->next = NULL; ListNode *p = list; while (p->next != NULL) p = p->next; p->next = node; }

void split(LinkList la, LinkList lb, LinkList lc, ElemType x) { ListNode *pa = la->next, *pb = lb, *pc = lc; while (pa) { if (pa->data <= x) { pb->next = pa; pb = pb->next; } else { pc->next = pa; pc = pc->next; }
pa = pa->next; } pb->next = NULL; pc->next = NULL; }

int main() { LinkList la = createList(), lb = createList(), lc = createList(); int n, x; scanf('%d', &n); for (int i = 0; i < n; i++) { scanf('%d', &x); insert(la, x); } scanf('%d', &x); split(la, lb, lc, x); ListNode *p = lb->next; int cnt = 0; while (p) { cnt++; p = p->next; } printf('%d\n', cnt); p = lb->next; while (p) { printf('%d', p->data); if (p->next) printf(' '); p = p->next; } printf('\n'); p = lc->next; cnt = 0; while (p) { cnt++; p = p->next; } printf('%d\n', cnt); p = lc->next; while (p) { printf('%d', p->data); if (p->next) printf(' '); p = p->next; } return 0; }

题目描述

给定一个单链表 'L' 和一个值 'x'，将 'L' 分成两个单链表 'L_1' 和 'L_2'，使得 'L_1' 中的所有结点的值小于等于 'x'，而 'L_2' 中的所有结点的值大于 'x'。

输入格式

第一行包含原始链表中结点的个数 'n'。

第二行包含 'n' 个整数，表示链表中的各结点的值。

第三行包含一个整数 'x'。

输出格式

输出两个链表 'L_1' 和 'L_2'。对于每个链表，首先输出链表的长度，然后输出链表中的所有整数，每个整数占一行。

数据范围

1 <= n <= 100000，-10^9 <= L_i <= 10^9，-10^9 <= x <= 10^9

输入样例：

10 9 8 7 6 5 4 3 2 1 0 3

输出样例：

4 2 1 0 6 5 4 3 9 8 7

算法1

(暴力枚举) O(n)

C++ 代码

// 暴力枚举
void split(LinkList la, LinkList lb, LinkList lc, ElemType x) {
    ListNode *p = la->next;
    while (p) {
        if (p->data <= x) {
            insert(lb, p->data);
        } else {
            insert(lc, p->data);
        }
        p = p->next;
    }
}

算法2

(暴力枚举) O(n)

blablabla

时间复杂度

参考文献

python3 代码

C++ 代码

java 代码

算法3

(暴力枚举) O(n)

blablabla

时间复杂度

参考文献

C++ 代码