You need to enable JavaScript to run this app. 如何比较两个单链表是否包含相同数据(不考虑元素存储顺序)
优惠活动
大模型
产品
解决方案
定价
更多

如何比较两个单链表是否包含相同数据(不考虑元素存储顺序)

链表相等判断(忽略元素顺序)实现方案

首先明确:你想的「遍历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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.12 12:42:04