PTA（链表）1-7 删除排序链表中的重复元素

1-7 删除排序链表中的重复元素

分数 7

作者 李廷元

单位 中国民用航空飞行学院

###题目描述：删除排序链表中的重复元素
编写一个函数，对于一个给定的排序链表，删除所有重复的元素每个元素只留下一个。

给出1->1->2->NULL，返回 1->2->NULL

给出1->1->2->3->3->NULL，返回 1->2->3->NULL

###单链表结点类型定义：

1
2
3
4
5
6
typedef int ElemType;    //元素的数据类型

typedef struct LNode {
    ElemType data;        //结点的数据域
    struct LNode *next;    //指向后继结点
} LinkNode;             //单链表结点类型

函数接口定义：

1
2
3
4
5
6
7
8
/*尾插法建立单链表,细节不表*/
LinkNode* CreateListR(ElemType a[], int n);

/*输出线性表,细节不表*/
void DispList(LinkNode *L);

/*删除排序链表中的重复元素*/
LinkNode* deleteDuplicates(LinkNode *L);

其中 L是单链表的头指针。 数组a[] 存放创建无序单链表的元素，n为数组长度，其值不超过10000。

裁判测试程序样例：

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
#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;    /*元素的数据类型*/

typedef struct LNode {    /*单链表结点类型定义*/
    ElemType data;        /*结点的数据域*/
    struct LNode *next;    /*指向后继结点*/
} LinkNode;             /*单链表结点类型*/

/*尾插法建立单链表,细节不表*/
LinkNode* CreateListR(ElemType a[], int n);

/*输出线性表,细节不表*/
void DispList(LinkNode *L);

/*删除排序链表中的重复元素*/
LinkNode* deleteDuplicates(LinkNode *L);

int main()
{    
    ElemType a[10000], x;
    int n = 0;

    while (scanf("%d", &x) != EOF) {
        a[n++] = x;
    }

    LinkNode* L = CreateListR(a, n);

    L = deleteDuplicates(L);
    DispList(L);

    return 0;
}

/* 请在下面填写答案 */

输入样例：

输入只有1行，在该行给出有序单链表的所有元素。

1
1 1 2 3 3

输出样例：

输出只有1行，在该行输出删除重复元素后的有序单链表，元素之间以一个空格分隔，行尾无多余的空格。

1
1 2 3

段错误和超时错误代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LinkNode* deleteDuplicates(LinkNode *L) {
    // 特殊情况：因为没有头结点，所以前面的元素如果有相同的，要特殊处理
    while (L->next != NULL) {
        if (L->data == L->next->data) {
            L = L->next;
        }
    }
    LinkNode *p = L->next; // 定义指针p便于遍历链表,指向next是因为第一个已经判断过了
    while (p->next != NULL) {
        if (p->data == p->next->data) {
            p->next = p->next->next; // 将相同的第二个跳过
        } else {
            p = p->next;
        }
    }
    return L;
}

段错误：

  • 如果只有11，完成第一个while循环之后，后面是NULL，若
1
2
3
LinkNode *p = L->next; 
    while (p->next != NULL) {
        if (p->data == p->next->data) {

  • L->next就是NULL了，再next就访问不了了

  • 加上if：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LinkNode* deleteDuplicates(LinkNode *L) {
    // 特殊情况：因为没有头结点，所以前面的元素如果有相同的，要特殊处理
    while (L->next != NULL) {
        if (L->data == L->next->data) {
            L = L->next;
        }
    }
    // 如果只有1：
    if (L->next == NULL) {
        return L;
    }
    LinkNode *p = L->next; // 定义指针p便于遍历链表,指向next是因为第一个已经判断过了
    while (p->next != NULL) {
        if (p->data == p->next->data) {
            p->next = p->next->next; // 将相同的第二个跳过
        } else {
            p = p->next;
        }
    }
    return L;
}

突然发现不需要分开处理：

正确代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LinkNode* deleteDuplicates(LinkNode *L) {
    // 1. 处理空链表：直接返回，避免空指针访问
    if (L == NULL) {
        return NULL;
    }

    // 2. 单指针遍历，无需单独处理头节点（利用链表有序性，重复节点必相邻）
    LinkNode *p = L;
    while (p->next != NULL) { // 遍历到倒数第二个节点，避免p->next为空
        if (p->data == p->next->data) { // 跳过重复节点，不移动p（继续检查新的p->next）
            p->next = p->next->next;
        } else { // 无重复，p后移
            p = p->next;
        }
    }

    return L;
}

简化逻辑：

利用 “链表有序，重复节点必相邻” 的特性，遇到重复时只需跳过p->next，无需移动p；无重复时p再后移，确保所有重复节点都被处理，且效率更高（时间复杂度O(n)，n为链表长度）。

  • 我分类是因为我认为头指针L和p有区别，如果全用p写，p往后了，但是L还是指向的之前的，但是实际上不是的：

问题：这不是只改变了p的指向吗，L的指向也改变了吗

代码中p是L的 “副本指针”，修改p的指向不会改变L的指向；但修改p->next（指针指向的节点内容），会直接改变原链表的结构，最终L作为表头指针，指向的仍是修改后链表的头部。

一、核心区别：“指针的指向” vs “指针指向的节点内容”

先理清两个关键概念，这是理解的核心：

  1. 指针的指向：比如LinkNode *p = L，这里p和L是两个独立的指针变量，它们的 “值” 都是 “链表头节点的地址”—— 相当于p和L都拿着 “头节点的门牌号”，但p是L的 “复印件”。
    • 若修改p的指向（如p = p->next），只是p的 “门牌号” 变了（指向了下一个节点），L的 “门牌号”（指向头节点）完全不变。
  2. 指针指向的节点内容：比如p->next = p->next->next，这里修改的不是p的指向，而是p当前指向的 “节点” 里的next成员（即节点的 “下一个门牌号”）。
    • 这个修改会直接改变原链表的连接关系（跳过重复节点），而L作为表头指针，指向的仍是修改后链表的第一个节点，自然能返回完整的修改后链表。

二、用例子拆解：以1->1->2为例

假设原链表是 1（头节点A）-> 1（节点B）-> 2（节点C）-> NULL，L指向头节点 A。

1. 初始化：LinkNode *p = L

  • p和L的指向相同，都指向头节点 A（拿着 A 的门牌号）。
  • 此时链表结构：L -> A -> B -> C -> NULL，p -> A。

2. 第一次循环：处理重复节点 A 和 B

  • 条件p->next != NULL（A 的next是 B，非空），且p->data == p->next->data（A 的 1 == B 的 1）。
  • 执行p->next = p->next->next：修改的是节点 A 的next成员—— 原本 A 的next指向 B，现在改为指向 C。
  • 此时链表结构变了：L -> A -> C -> NULL（B 节点被跳过，相当于删除了重复的 B）。
  • 注意：p的指向仍未变（还是指向 A），L的指向也未变（仍指向 A）。

3. 第二次循环：处理 A 和 C（无重复）

  • 条件p->next != NULL（A 的next是 C，非空），但p->data != p->next->data（A 的 1 != C 的 2）。
  • 执行p = p->next：修改p的指向，让p从 A 指向 C（p的 “门牌号” 变了，但L仍指向 A）。

4. 第三次循环：终止

  • p现在指向 C，p->next == NULL（C 的next是 NULL），循环终止。
  • 最终L仍指向头节点 A，返回的L对应的链表是A -> C -> NULL（即1->2），完全符合需求。

三、结论

  • L的指向从未改变：L自始至终都指向原链表的头节点（除非头节点本身是重复节点且需要删除，但本题中 “保留第一个重复节点”，头节点若不重复，L就一直指向它）。
  • p的作用是 “遍历工具”：p的指向变化只是为了遍历链表的每个节点，而真正修改链表结构的是p->next的调整 —— 这种方式既高效又能保证L作为表头指针的正确性。