【面试必刷TOP101】面试官：如何删除有序链表中重复的元素？

🍳作者：

      贤蛋大眼萌，一名很普通但不想普通的程序媛
     
    
   
   
    \color{#FF0000}{贤蛋 大眼萌 ，一名很普通但不想普通的程序媛}
   
  
 贤蛋大眼萌，一名很普通但不想普通的程序媛🤳

🙊语录：

      多一些不为什么的坚持
     
    
   
   
    \color{#0000FF}{多一些不为什么的坚持}
   
  
 多一些不为什么的坚持

📓 专栏：牛客刷题–斩获offer

💭

       眼过千遍不如手锤一遍：推荐一款模拟面试，斩获大厂
      
      
       o
      
      
       f
      
      
       f
      
      
       e
      
      
       r
      
      
       ，程序员的必备刷题平台
      
      
       −
      
      
       −
      
      
       牛客网
      
     
    
   
   
    \color{#ff7f50}{眼过千遍不如手锤一遍：推荐一款模拟面试，斩获大厂offer，程序员的必备刷题平台--牛客网}
   
  
 眼过千遍不如手锤一遍：推荐一款模拟面试，斩获大厂offer，程序员的必备刷题平台−−牛客网

👉🏻开启刷题之旅

如何删除有序链表中重复的元素？

🧨 前言

🚀

      牛客网
     
    
   
   
    \color{#ff7f50}{牛客网}
   
  
 牛客网 是一个集笔面试系统、题库、课程教育、社群交流、招聘内推于一体的招聘类网站，更是一个专注于程序员的学习和成长的平台。

🪓自学是一个程序员必备的能力，而提高自己的编程能力最好方法就是通过刷题。一次偶然的机会让我发现牛客网这个新大陆，开启自己IT之旅。

这里有个大厂的面试真题，知己知彼百战百胜。

更有在线编程调试功能，提高编程效率。👉🏻开始学习

🎁 正文

① 删除有序链表中重复的元素-I

描述（题目简单） 考点：链表

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1-> 1-> 2，返回1 ->2
给出的链表为1→1→2→3→3,返回1→2→3.

解题思路：

​ 根据题意，我们分析，要删除有序链表当中重复的元素使所有重复元素只出现一次，在这个过程当中，可以选定两个链表指针i和j，通过设定i为head，j为i.next，依次通过循环将重复元素的个数减为0，如果没有发现重复的元素，令j = j.next，再次进行判断；如果发现有重复元素，令i.next = j.next，除掉重复元素，依次递归进行判断。

题解：

// 语言①：c 
struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL) {
        return head;
    }
    struct ListNode* p = head;
    while (p->next != NULL) {
        if (p->val == p->next->val) { //相邻数据相等时
            p->next = p->next->next;//相等的数据的第一个的指针指向不相等的数据元素
        } else {
            p = p->next;
        }
    }
    return head;
}

//语言②：JavaScript/*
  遍历链表，比较当前与下一个的值是否相等，如相等，把当前的下一个指向下一个的下一个。这里有两点要注意：1.要判断next以及next.next是否存在；2.只有值不相等遍历指针才往下走。
  */functiondeleteDuplicates(head){// write code herelet current = head;while(current){if(current.next && current.val == current.next.val){if(current.next.next){
        current.next = current.next.next;}else{
        current.next =null;}}else{
      current = current.next;}}return head;}
module.exports ={deleteDuplicates: deleteDuplicates,};

② 删除有序链表中重复的元素-II

描述（题目较难） 考点：链表

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.

数据范围：链表长度 100000≤n≤10000，链表中的值满足 |val| ≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

解题思路：

​ 可以利用双指针法，首先我们可以设置一个newhead对象，pre = newhead，cur = head，在已知head的情况下，我们开始循环判断cur对象，设置循环条件为cur ->next不为空，判断cur->val是否等于cur->next->val，如果等于就将count的值累加（其中count的值为链表中的重复累加元素的个数和），当有重复的情况发生，就令pre->next = cur->next，count = 0，删除该元素，始终进行如下判断，如果没有重复，就将pre链表的值变为现在cur链表的值，递归条件为cur = cur - next。

1.首先加上一个空的头结点，便于处理删除第一个结点的情况。

2.需要设一个pre指针跟踪工作结点及记录一路留下来的结点。

3.用2个指针p,q来比较结点值是否相同。

4.不同时，pre指向p，p指向q，q指向q->next。

5.相同时，继续看q的后面是否还有一样，直到找到不同的，或者到链尾。

a,若后面还有不同的，则更换pre,p,q指针的指向，继续比较。

b,若q值后面一直到链尾没有不同的，那么从p到q都要删掉，pre指空完结。

题解：

//语言① ：cstructListNode*deleteDuplicates(structListNode* head ){structListNode* L =(structListNode*)malloc(sizeof(structListNode));//新建结点
    L->next = head;//指针域置空if(head ==NULL|| head->next ==NULL)return head;//0个或1个元素时不会有重复的元素，原样返回即可structListNode* pre = L;//前驱指针structListNode* p = head;structListNode* q = head->next;while(q !=NULL){if(q->val != p->val){//不同值时均后移
              pre = p;   
              p = q;
              q = q->next;}else{while(q->next->val == q->val && q->next !=NULL)
                 q = q->next;//后面还有相同值时继续后移if(q->next ==NULL){//竟然一直移到了末尾
                pre->next =NULL;//从p到q全部不要return L->next;//提前返回}
             p = q->next;//略过重复元素，重新开始比较
             pre->next = p;//前驱也要同步跟上
             q = p->next;}}return L->next;}

// 语言②：JavaScriptfunctiondeleteDuplicates(head){// write code hereif(head ==null)return head;const dummyNode =newListNode(-1);
  dummyNode.next = head;let cur = dummyNode;while(cur.next && cur.next.next){if(cur.next.val === cur.next.next.val){const temp = cur.next.val;while(cur.next && cur.next.val === temp){
        cur.next = cur.next.next;}}else{
      cur = cur.next;}}return dummyNode.next;}

🎉 总结

求知无坦途，学问无捷径。👣

      一步一个脚印，你走过的路，每一步都算数。
     
    
   
   
    \color{#ff7f50}{一步一个脚印，你走过的路，每一步都算数。}
   
  
 一步一个脚印，你走过的路，每一步都算数。 每一次进步都是对自己努力的肯定。如果读了文章有收获，不如一起来学习，一起进步吧。传送门🚪刷题神器