如何比较两个单链表是否包含相同数据(不考虑元素存储顺序)
链表相等判断(忽略元素顺序)实现方案
首先明确:你想的「遍历ll1的每一次迭代同步遍历ll2直接对比」的思路是行不通的,因为两个链表的元素存储顺序没有对应关系,无法按位置匹配元素,正确实现逻辑如下:
实现逻辑
- 第一步:分别统计两个链表的长度,如果长度不一致直接判定为不相等,无需后续判断
- 第二步:长度一致的前提下,遍历第一个链表的所有元素做匹配标记
- 第三步:遍历第二个链表的每个元素,去第一个链表中查找未匹配的相等元素,找到就打标记,找不到直接判定不相等
- 第四步:第二个链表遍历完成后所有元素都能找到对应匹配项,就判定两个链表相等
代码实现
你给出的结构体定义如下:
typedef struct Node{ char key[100]; char data[100]; struct Node *next; }node;
工具函数实现
#include <stdio.h> #include <stdlib.h> #include <string.h> // 统计链表长度 int get_length(node *head) { int len = 0; while(head != NULL) { len++; head = head->next; } return len; } // 判断两个节点的存储内容是否完全相等 int is_node_equal(node *a, node *b) { // 同时匹配key和data,若只需匹配其中一个字段可自行调整逻辑 return (strcmp(a->key, b->key) == 0 && strcmp(a->data, b->data) == 0); }
主判断函数
以下实现适用于中小规模的链表,逻辑简单无需引入额外数据结构:
int is_linked_list_equal(node *ll_1, node *ll_2) { int len1 = get_length(ll_1); int len2 = get_length(ll_2); // 长度不同直接返回不相等 if (len1 != len2) return 0; // 标记数组,记录ll_1中已经匹配过的节点下标 int *matched = (int *)calloc(len1, sizeof(int)); node *p1 = NULL; node *p2 = ll_2; int res = 1; while (p2 != NULL) { int found = 0; p1 = ll_1; // 遍历ll_1找未匹配的相等节点 for (int i = 0; i < len1; i++) { if (matched[i] == 0 && is_node_equal(p1, p2)) { matched[i] = 1; found = 1; break; } p1 = p1->next; } // 找不到对应节点直接返回不相等 if (!found) { res = 0; break; } p2 = p2->next; } free(matched); return res; }
优化说明
如果你的链表长度很大,上述O(n²)时间复杂度的实现性能较低,可以引入哈希表统计每个元素的出现次数,遍历ll_1统计次数、遍历ll_2扣减次数,就能把时间复杂度降到O(n)。
内容的提问来源于stack exchange,提问作者miweomnwirng
相关产品推荐
相关产品推荐

