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

🍳作者：$贤蛋大眼萌，一名很普通但不想普通的程序媛$🤳

🙊语录：$多一些不为什么的坚持$

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

💭$眼过千遍不如手锤一遍：推荐一款模拟面试，斩获大厂offer，程序员的必备刷题平台--牛客网$

👉🏻开启刷题之旅

🧨 前言

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

🪓自学是一个程序员必备的能力，而提高自己的编程能力最好方法就是通过刷题。一次偶然的机会让我发现牛客网这个新大陆，开启自己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.只有值不相等遍历指针才往下走。
  */
function deleteDuplicates(head) {
  // write code here
  let 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指空完结。

题解：

//语言① ：c
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    struct ListNode* L =(struct ListNode*)malloc(sizeof(struct ListNode));  //新建结点
    L->next = head;  //指针域置空
    if(head == NULL || head->next == NULL)
        return head;  //0个或1个元素时不会有重复的元素，原样返回即可
    struct ListNode* pre = L;   //前驱指针
    struct ListNode* p = head;   
    struct ListNode* 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;
}

// 语言②：JavaScript
function deleteDuplicates(head) {
  // write code here
  if (head == null) return head;
  const dummyNode = new ListNode(-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;
}

🎉 总结

求知无坦途，学问无捷径。👣$一步一个脚印，你走过的路，每一步都算数。$ 每一次进步都是对自己努力的肯定。如果读了文章有收获，不如一起来学习，一起进步吧。传送门🚪刷题神器