c - 循环链表中两个节点之间的距离

Question

我想找到循环链表中两个节点之间的距离(它们之间的节点数)。

节点在哪里:

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

nodal *distance(nodal *start)
{
    int n1,n2,d1=0,d2=0,c=0;
    if(start==NULL)
    {
        printf("\nList is empty");
    }
    else
    {
        printf("\nEnter the fist node element : ");
        scanf("%d",&n1);
        printf("\nEnter the second node element : ");
        scanf("%d",&n2);
        nodal *ptr=start;
        while(ptr->next!=start)
        {
            c++;
            if(ptr->data==n1)
            {
                d1=c;
            }
            if(ptr->data==n2)
            {
                d2=c;
            }
        }
    }
    printf("The distance between two nodes is %d",(d2-d1));
    return start;
}

我没有给出任何输出。

还假设循环列表包含以下数据:

1,2,3,4,5,6,7,8,9

如果我提供输入

First node element as 9

Second node element as 4

那么这个算法就不行了。 对于改变有什么建议吗？

Answer 1

当找到第一个节点时开始计数，当找到第二个节点时停止计数，如下所示:

int inc = 0, dist = 0;

if (n1 == n2) {
    return 0;
}
node = start;
while (node) {
    dist += inc;
    if ((node->data == n1) || (node->data == n2)) {
        if (inc++ == 1) return dist;
    }
    node = node->next;
    if (node == start) break;
}
return 0;