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

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;

Answer 2

首先要到输入的第一个元素，这个过程中计数不会增加。然后开始递增计数，直到到达第二个元素。

代码如下：

ptr=start;
while(ptr->data!=n1)
{
   ptr=ptr->next;
}
//---now we have reached the first number----

while(ptr->data!=n2)
{
  count++;
ptr=ptr->next;
}

Answer 3

您的代码中存在多个问题：

列表末尾的测试阻止您测试最后一个节点。
您通过返回 0 来处理 n1 == n2 的情况，这可能不是预期的。
如果n2出现在n1之前，n1和n2之间的距离将为负，这是不正确的：因为列表是循环的，如果你一直扫描在n1之后，绕过第一个节点后，你最多会在正距离遇到n2。

这是另一种解决方案：

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

nodal *distance(nodal *start) {
    int n1, n2, d1 = 0, d2 = 0, length = 0;
    if (start == NULL) {
        printf("List is empty\n");
    } else {
        printf("\nEnter the fist node element : ");
        if (scanf("%d", &n1) != 1) {
            printf("invalid input\n");
            return start;
        }
        printf("\nEnter the second node element : ");
        if (scanf("%d", &n2) != 1) {
            printf("invalid input\n");
            return start;
        }
        nodal *ptr = start;
        for (;;) {
            length++;
            if (ptr->data == n1 && !d1) {
                d1 = length;
            } else if (ptr->data == n2) {
                if (d1) {
                    d2 = length;
                    break;
                }
                if (!d2)
                    d2 = length;
            }
            ptr = ptr->next;
            if (ptr == start)
                break;
        }
    }
    if (d1 && d2) {
        int dist = d2 - d1;
        if (dist < 0)
            dist += length;
        printf("The distance between node(%d) and node(%d) is %d\n", d1, d2, dist);
    } else {
        if (d2)
            printf("node(%d) not found\n", d1);
        if (d1)
            printf("node(%d) not found\n", d2);
    }
    return start;
}

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

Distance between two nodes in circular linked list

c

linked-list

circular-list

data-structures