面试题：C语言指针关系运算在复杂数据结构中的应用

Question

假设有一个链表结构定义如下： ```c struct Node { int data; struct Node *next; }; ``` 现在有两个指针 `struct Node *head1` 和 `struct Node *head2` 分别指向两个不同链表的头节点。两个链表可能存在部分节点是共享的（即相同的内存地址）。请编写一个函数 `int compareLists(struct Node *head1, struct Node *head2)`，利用指针关系运算来判断两个链表从开始到第一个共享节点（如果存在），哪一个链表更长（节点数更多），并返回相应结果（例如，返回1表示 `head1` 链表更长，返回 - 1表示 `head2` 链表更长，返回0表示长度相同）。如果两个链表没有共享节点，函数返回 -2。要求考虑各种边界情况。

Answer 1

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

int compareLists(struct Node *head1, struct Node *head2) {
    struct Node *ptr1 = head1, *ptr2 = head2;
    int len1 = 0, len2 = 0;

    // 计算head1链表长度
    while (ptr1 != NULL) {
        len1++;
        ptr1 = ptr1->next;
    }

    // 计算head2链表长度
    while (ptr2 != NULL) {
        len2++;
        ptr2 = ptr2->next;
    }

    ptr1 = head1;
    ptr2 = head2;

    // 寻找共享节点
    while (ptr1 != NULL && ptr2 != NULL && ptr1 != ptr2) {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }

    // 如果没有共享节点
    if (ptr1 != ptr2) {
        return -2;
    }

    if (len1 > len2) {
        return 1;
    } else if (len1 < len2) {
        return -1;
    } else {
        return 0;
    }
}