当前位置: 首页 > 文档资料 > LeetCode 题解 >

Linked List - Remove Duplicates from Sorted List

优质
小牛编辑
124浏览
2023-12-01

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,

Given 1->1->2, return 1->2.

Given 1->1->2->3->3, return 1->2->3.

这题要求在一个有序的链表里面删除重复的元素,只保留一个,也是比较简单的一个题目,我们只需要判断当前指针以及下一个指针时候重复,如果是,则删除下一个指针就可以了。

代码如下:

  1. class Solution {
  2. public:
  3. ListNode *deleteDuplicates(ListNode *head) {
  4. if(!head) {
  5. return head;
  6. }
  7. int val = head->val;
  8. ListNode* p = head;
  9. while(p && p->next) {
  10. if(p->next->val != val) {
  11. val = p->next->val;
  12. p = p->next;
  13. } else {
  14. //删除next
  15. ListNode* n = p->next->next;
  16. p->next = n;
  17. }
  18. }
  19. return head;
  20. }
  21. };

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,

Given 1->2->3->3->4->4->5, return 1->2->5.

Given 1->1->1->2->3, return 2->3.

这题需要在一个有序的链表里面删除所有的重复元素的节点。因为不同于上题可以保留一个,这次需要全部删除,所以我们遍历的时候需要记录一个prev节点,用来处理删除节点之后节点重新连接的问题。

代码如下:

  1. class Solution {
  2. public:
  3. ListNode *deleteDuplicates(ListNode *head) {
  4. if(!head) {
  5. return head;
  6. }
  7. //用一个dummy节点来当做head的prev
  8. ListNode dummy(0);
  9. dummy.next = head;
  10. ListNode* prev = &dummy;
  11. ListNode* p = head;
  12. while(p && p->next) {
  13. //如果没有重复,则prev为p,next为p->next
  14. if(p->val != p->next->val) {
  15. prev = p;
  16. p = p->next;
  17. } else {
  18. //如果有重复,则继续遍历,直到不重复的节点
  19. int val = p->val;
  20. ListNode* n = p->next->next;
  21. while(n) {
  22. if(n->val != val) {
  23. break;
  24. }
  25. n = n->next;
  26. }
  27. //删除重复节点
  28. prev->next = n;
  29. p = n;
  30. }
  31. }
  32. return dummy.next;
  33. }
  34. };