如何计算循环链表中两个节点之间的距离？

首先明确需求：我们要实现一个函数，计算循环链表中两个指定节点之间的距离（即两节点之间的节点数量）。给定的节点结构体定义如下：

typedef struct node { 
    int data; 
    struct node *next; 
} nodal;

你已经写了distance函数的开头部分，我来帮你补全完整实现，同时处理各种边界情况（比如链表为空、找不到指定节点、两个节点为同一个等）：

nodal *distance(nodal *start) { 
    int n1, n2, d1 = 0, d2 = 0, c = 0; 
    if(start == NULL) { 
        printf("\nList is empty"); 
        return start; // 空链表直接返回
    } 
    else { 
        printf("\nEnter the first node element : "); 
        scanf("%d", &n1); 
        printf("\nEnter the second node element : "); 
        scanf("%d", &n2); 

        nodal *ptr = start; 
        // 遍历找n1的位置，记录从start到n1的节点数
        do {
            if(ptr->data == n1) {
                break;
            }
            d1++;
            ptr = ptr->next;
        } while(ptr != start); // 循环链表遍历终止条件是回到起点

        // 检查是否找到n1
        if(ptr->data != n1) {
            printf("\nNode with data %d not found in the list", n1);
            return start;
        }

        // 保存n1对应的节点指针
        nodal *node1 = ptr;
        ptr = start;

        // 遍历找n2的位置，记录从start到n2的节点数
        do {
            if(ptr->data == n2) {
                break;
            }
            d2++;
            ptr = ptr->next;
        } while(ptr != start);

        // 检查是否找到n2
        if(ptr->data != n2) {
            printf("\nNode with data %d not found in the list", n2);
            return start;
        }

        // 从n1出发计算到n2的距离
        ptr = node1;
        while(ptr->data != n2) {
            c++;
            ptr = ptr->next;
        }

        printf("\nDistance between %d and %d is %d", n1, n2, c);

        // 这里返回start，也可以根据需求返回node1或其他节点指针
        return start;
    }
}

关键逻辑说明： #

• 空链表处理：先判断链表是否为空，直接提示错误并返回。
• 循环链表遍历：用do-while循环保证至少遍历一次，适配循环链表“起点即终点”的特性。
• 节点存在性校验：遍历完整个链表仍未找到目标节点时，给出明确提示。
• 距离计算：从第一个目标节点出发，遍历到第二个目标节点，记录的步数就是两者之间的距离；若两个节点是同一个，距离会自动计算为0。

另外要注意：如果链表中存在多个data值相同的节点，这段代码会匹配第一个出现的节点。如果需要处理重复节点场景，可以考虑修改函数参数为节点指针，或者增加额外的位置指定逻辑。

内容的提问来源于stack exchange，提问作者Vivank