PTA（链表）1-9 共享后缀的链表

1-9 共享后缀的链表

分数 6

作者 陈越

单位 浙江大学

有一种存储英文单词的方法，是把单词的所有字母串在一个单链表上。为了节省一点空间，如果有两个单词有同样的后缀，就让它们共享这个后缀。下图给出了单词“loading”和“being”的存储形式。本题要求你找出两个链表的公共后缀。

fig.jpg

函数接口定义：

1
PtrToNode Suffix( List L1, List L2 );

其中List结构定义如下：

1
2
3
4
5
6
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L1和L2都是给定的带头结点的单链表。函数Suffix应返回L1和L2的公共后缀的起点位置。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

void ReadInput( List L1, List L2 ); /* 裁判实现，细节不表 */
void PrintSublist( PtrToNode StartP ); /* 裁判实现，细节不表 */
PtrToNode Suffix( List L1, List L2 );

int main()
{
    List L1, L2;
    PtrToNode P;

    L1 = (List)malloc(sizeof(struct Node));
    L2 = (List)malloc(sizeof(struct Node));
    L1->Next = L2->Next = NULL;
    ReadInput( L1, L2 );
    P = Suffix( L1, L2 );
    PrintSublist( P );

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

1
如图存储的链表

fig.jpg

输出样例：

1
ing

我的思路

  • 从一个表出发，从第一个结点开始，依次比较第二个表的各个结点，找到除开NULL的第一个相同的就是共享后缀的地方
  • 但我感觉时间复杂度会很高，我也还没想到其他简单一点的算法，我先试试：

我的超时代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
PtrToNode Suffix( List L1, List L2 ) {
    List p = L1->Next; // p用于遍历链表L1
    List q = L2->Next; // q用于遍历链表L2
    while (q != NULL) {
        while (p != NULL) {
            if (q == p) { // 如果循环到地址相同的，就返回该相同的地址
                return q;
            }
            // 否则p往后遍历
            p = p->Next;
        }
        // p遍历过一遍之后没有的话，往后遍历一次
        q = q->Next;
        // p指针重置
        p = L1->Next;
    }
    // 没找到
    return NULL;
}

  • 果然：

    测试点 内存(KB) 用时(ms) 结果 得分
    0 556 1 答案正确 1 / 1
    1 516 1 答案正确 1 / 1
    2 564 1 答案正确 1 / 1
    3 576 1 答案正确 1 / 1
    4 528 1 答案正确 1 / 1
    5 3296 200 运行超时 0 / 1

正确代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 计算链表长度
int getLength(List L) {
    int len = 0;
    List p = L->Next; // 指向第一个结点
    while (p != NULL) {
        len++;
        p = p->Next;
    }
    return len;
}

PtrToNode Suffix( List L1, List L2 ) {
    int len1 = getLength(L1);
    int len2 = getLength(L2);
    List p = L1->Next; // p用于遍历链表L1
    List q = L2->Next; // q用于遍历链表L2
    // 让较长的链表先走，使剩余长度相同
    if (len1 > len2) {
        for (int i = 0; i < len1 - len2; i++) {
            p = p->Next;
        }
    } else {
        for (int i = 0; i < len2 - len1; i++) {
            q = q->Next;
        }
    }

    // 同步遍历，找第一个地址相同的节点
    while (p != NULL && q != NULL) {
        if (p == q) {
            return p; // 找到公共后缀起点
        }
        p = p->Next;
        q = q->Next;
    }

    return NULL; // 无公共后缀
}

正确思路：先对齐长度，再同步遍历

要高效找到公共后缀，需利用 “公共后缀长度相同” 的特性，步骤如下：

  1. 计算两个链表的长度 len1 和 len2。
  2. 让较长的链表先走 |len1 - len2| 步，使两个链表剩余长度相同。
  3. 同步遍历两个链表，找到第一个地址相同的节点（公共后缀的起点）。

对比

  1. 时间复杂度优化：通过先对齐长度，再同步遍历，时间复杂度降为 (O(N + M))，效率大幅提升。
  2. 修复逻辑漏洞：每次同步遍历时，p 和 q 都从 “剩余长度相同” 的位置开始，确保能正确比较所有可能的节点。
  3. 正确性保证：公共后缀的节点地址必然相同（题目中 “共享后缀” 即节点共享），因此比较地址即可找到公共后缀的起点。