首页 > 代码库 > Remove Duplicates from Sorted List II leetcode
Remove Duplicates from Sorted List II leetcode
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
.
题目的意思是将链表中出现了重复元素的节点全部删除 由于可能出现将第一个节点删除的情况,需要重新new一个节点
上以篇中是将 链表中出现了重复的元素只保留一份 , Remove Duplicates from Sorted List leetcode
思路:
定义三个指针 pur p q pur用来指向 需要删除的前一个节点 p用来指向需要删除的第一个节点 q用来指向需要删除的最后一个节点的下一个节点
如 上 1->1->1->2->3 开始时 pur 为new的新节点 p为 第一个1 q为 2
这个程序中需要注意,删除是在 p->val 不等于 q->val时进行的(相等时 q需要往后遍历找到不相等的), p可能需要删除,也可能不删除
删除的理由: 一开始 p->val == q->val 但是q往后遍历 q值变了 需要删除p 所以我们设定一个标识 k 用来记录刚开始有没有p->val==q->val的情况
代码如下:
/** * 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) { if(head==NULL||head->next==NULL) return head; ListNode *result=new ListNode(0); result->next=head; ListNode *p,*q,*pur; //定义三个指针 pur用来表示删除的前一个元素,p表示需要删除元素的第一个,q表示需要删除元素的最后一个 pur=result; p=result->next; q=p->next; int k=0; //标记 p是否要删除 初始值为0 如 1 2 2 这里 pur为1 p为 2 所以p需要删除 while(q!=NULL) { if(p->val==q->val) { q=q->next; k=1; //用来标记p是否也要删除 } else if(p->val!=q->val&&k==1)//表示p也要删除 { pur->next=q; //删除 p=q; //重新设置p q q=q->next; k=0; //重置k } else if(p->val!=q->val&&k==0) //表示p不用删除 { pur=p; p=q; q=q->next; } } if(k==1) //k=1 表示链表遍历最后面有相等的,表示最后的元素都需要删除 如 1 2 2 这里 2 2都要删除 pur->next=q; return result->next; } };
Remove Duplicates from Sorted List II leetcode