C语言力扣刷题7——删除排序链表中的重复元素 II——[快慢双指针法]

一、博客声明

  找工作逃不过刷题，为了更好的督促自己学习以及理解力扣大佬们的解题思路，开辟这个系列来记录。代码可能不是自己写的，不求方法最好，只求更多地理解大佬们的解题思路。

---

二、题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按 升序 排列

---

三、解题思路

1、思路说明

  这题使用了快慢指针双指针去做，具体可以看下面这张图片，fast指针跑的快，slow跑的慢，beforeSlow为slow的上一个节点。通过判断nums[fast]和nums[slow]是否相同，期间需要定义一个标志位flag来记录当两者不同的时候，中间是否存在相同的数，如下面遍历到第二个阶段nums[slow] = 3, nums[fast] = 4中间就存在3是重复数，因此要执行删除的操作。beforeSlow存在的意义就是防止链表是重复数结尾，如果是重复数结尾，那slow就停止了重复的第一个数上，这个数字也是要删除了，为了不重新遍历一遍，就直接让beforeSlow是slow的上一个节点，直接让beforeSlow->next = NULL。

 

---

四、解题代码（附注释）

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(head == NULL || head->next == NULL){ //如果链表节点长度小于等于1，直接返回head；
        return head;
    }
    struct ListNode* preHead = malloc(sizeof(struct ListNode));//建立一个检查头
    preHead->val = 0;
    preHead->next = head;
    struct ListNode* slow = preHead->next;//定义慢指针
    struct ListNode* fast = preHead->next->next;//定义快指针
    struct ListNode* beforeSlow = preHead;//定义慢指针的前一个节点
    int flag = 0;//一个标志位，用于标记快慢指针是否正在重复
    while(fast){
        if(fast->val == slow->val){
            flag = 1; //快慢指针经历重复数，标志位置1
            fast = fast->next; // 快指针移动
            if(fast == NULL){  // 如果到了节点末尾，说明是重复数结尾，
                beforeSlow->next = NULL;//因此慢指针的前一个节点的next需要指向NULL,然后break
                break;
            }
            continue;
        } else {
            if(flag == 0){ //标志位为0，说明不是经历重复数后判断的不同，因此慢指针移动
                slow = slow->next;
                beforeSlow = beforeSlow->next;
            } else {// 否则 slow = fast ， 将标志位置0
                slow->val = fast->val;
                slow->next = fast->next;
                flag = 0;
            }
        }

        fast = fast->next;// 快指针移动
    }
    struct ListNode* result = preHead->next;
    free(preHead);
    return result;
}
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