题目要求
给定一个有序链表,删除所有的重复数字,仅仅留下非重复数字。
注意:和题目
leetcode83. Remove Duplicates from Sorted List(删除有序链表中的重复项)的区别。
示例
//Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5 // 删掉重复的数字3,4//Example 2:
Input: 1->1->1->2->3
Output: 2->3 // 删掉重复的数字1
解题思路
本题目最大的难点即和83题的不同就是,需要把所有的重复都删除,如:EX1中删除重复的3,4(且不保留任意一个3,4).在83题中,我们通过
p->next = p->next->next 可以通过去除重复数字的后一个数,达到去除相邻元素重复的目的。但是同时却不能去除前一个重复数字。这是本题目中所不允许的。
因为要全部删除重复的数字,所以我们想到可以通过记录重复数字的前驱结点,以及重复数字的值,来循环的进行删除节点。还通过这个公式进行删除,
p->next = p->next->next 但是比较的不是当前遍历元素的值和下一个元素的值。而是当前元素后两个值之间的关系,这样就可以把当前元素作为一个前驱结点进行看待 然后再进行一个循环删除的操作,当前元素后边所有重复的点都删除,直到遇到非重复数字,进行后移。
过程说明
以 1-2-3-3-4-4-5 为例子,来说明思路的实现流程,当遍历到2的时候,发现他的后两个元素都是3,此时首先记下重复元素是3,然后进行删除第一个3。
这时链表变成1-2-3-4-4-5,回到2,判断他的下一个数字是3(是记录的重复元素),所以再删掉。
此时链表变成1-2-4-4-5,然后回到2,发现他的后两个元素是4,然后进行和上面一样的操作,连续删除两个4.
这时候链表变成1-2-5,因不符合循环的条件而返回。
主要代码c++
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {
ListNode *dummpy = new ListNode(0); // 建造傀儡节点dummpy->next = head;ListNode *p = dummpy;int dup; while(p->next && p->next->next){
if(p->next->val == p->next->next->val)// 有重复{
dup = p->next->val; //记录重复的数值while(p->next&&p->next->val == dup)//下一点是重复值那么删掉p->next = p->next->next;}else{
p = p->next; //下一节点不是重复点那么,向后移动}} return dummpy->next; }
};