首页 > 代码库 > leetcode - Remove Duplicates from Sorted List II
leetcode - 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.
题目的意思是将重复的结点全部删除，只留下不重复的结点，并且结点是排好序的
个人思路：
1，从链表头部开始遍历，设置3个指针，一个是current，表示当前结点，另一个是currentBefore，表示当前结点的上一个结点，最后一个是probe，表示当前结点的下一个结点，probe用于探索下面的结点是否和当前结点相同；
2，若相同，则删除probe结点，并且继续往下探索，直到probe结点和current结点不同，此时还得删除current结点，然后重新设置好这3个指针；若不同，则重新设置好这3个指针，继续往下遍历即可
3，注意一下头节点的处理
代码：
1 #include <stddef.h> 2 3 struct ListNode 4 { 5 int val; 6 ListNode *next; 7 ListNode(int x) : val(x), next(NULL) {}; 8 }; 9 10 class Solution {11 public:12 ListNode *deleteDuplicates(ListNode *head) {13 if (!head)14 {15 return NULL;16 }17 18 ListNode *current = head;19 ListNode *currentBefore = NULL;20 ListNode *probe = NULL;21 bool isDeleted;22 23 while (current)24 {25 isDeleted = false;26 probe = current->next;27 while (probe && probe->val == current->val) //删除相同的结点28 {29 current->next = probe->next;30 delete probe;31 probe = current->next;32 isDeleted = true;33 }34 if (isDeleted)35 {36 if (current == head)37 {38 delete current;39 current = probe;40 head = current;41 }42 else43 {44 currentBefore->next = probe;45 delete current;46 current = currentBefore->next;47 }48 }49 else50 {51 currentBefore = current;52 current = probe;53 }54 }55 56 return head;57 }58 };
leetcode - Remove Duplicates from Sorted List II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。