如何比较两个单链表判断是否存在包含关系?现有实现因篡改节点值导致链表异常
链表包含关系判断的实现优化
现有实现的硬伤
- 最初的逻辑设计是判断较短链表的所有元素是否能被较长链表完全匹配,通过交换比较函数入参复用同一套匹配流程,用
number_elem统计短链表长度作为匹配成功的阈值 - 为了避免长链表的同一个元素被重复计数,原实现直接把匹配过的长链表节点值改成
2147483647的哨兵值,直接篡改了原始链表的内存数据,流程跑完之后原始链表的内容已经被破坏,根本没法继续用 - 相比你想到的“新建链表拷贝原始数据再比较”的方案,纯游标指针的匹配方式没有额外堆内存开销,也不需要在比较结束后手动释放拷贝的内存,不会引入内存泄漏的隐患
优化方案
完全不需要拷贝链表,靠移动游标指针就能完成匹配,全程不碰原始节点的存储值:
- 先分别统计两个链表的有效长度,固定更短的链表为待匹配基准,更长的为被匹配对象
- 从长链表的第一个节点开始,逐节点当匹配起点,和短链表从头部开始逐一对齐
- 只要某次连续比对的命中数等于短链表的总长度,就判定为存在包含关系
修正后可参考的实现代码
#include <stdlib.h> #include <stdio.h> struct uzel { int n; struct uzel *next; }; struct uzel* initialize(struct uzel *head) { int a; printf("uzel = "); scanf("%d", &a); if (a == 0) { head->n = 0; head->next = NULL; return head; } else { head->n = a; head->next = malloc(sizeof(struct uzel)); return initialize(head->next); } } void gprint(struct uzel *head) { printf("("); while (head != NULL && head->next != NULL) { printf("%d ", head->n); head = head->next; } printf(")\n"); } // 纯游标比对,不修改任何原始节点值 int compare(struct uzel *short_list, struct uzel *long_list, int short_len) { struct uzel *long_cursor = long_list; while (long_cursor != NULL) { struct uzel *short_cursor = short_list; struct uzel *long_temp = long_cursor; int match_count = 0; while (long_temp != NULL && short_cursor != NULL) { if (long_temp->n == short_cursor->n) { match_count++; long_temp = long_temp->next; short_cursor = short_cursor->next; if (match_count == short_len) { return 1; } } else { break; } } long_cursor = long_cursor->next; } return 0; } int number_elem(struct uzel* head) { int cnt = 0; struct uzel *kolvo = head; while (kolvo != NULL && kolvo->next != NULL) { cnt++; kolvo = kolvo->next; } return cnt; } int main() { struct uzel head1; initialize(&head1); int len1 = number_elem(&head1); printf("链表1长度:%d\n", len1); gprint(&head1); struct uzel head2; initialize(&head2); int len2 = number_elem(&head2); printf("链表2长度:%d\n", len2); gprint(&head2); printf("开始校验链表包含关系\n"); int is_contain = 0; if (len1 <= len2) { is_contain = compare(&head1, &head2, len1); } else { is_contain = compare(&head2, &head1, len2); } printf(is_contain ? "YES\n" : "NOPE\n"); // 比对完成后打印原始链表,验证数据未被篡改 gprint(&head1); gprint(&head2); return 0; }
内容的提问来源于stack exchange,提问作者Alisove
相关产品推荐
相关产品推荐

