【题目】
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:
遍历链表,记录重复元素的起始位置和截止位置。要删除的重复元素的上一个位置begin,截止位置end。例如:1,2,2,2,4 begin = 0 end = 3
如果当前元素和上一个元素相等,则更新end;如果不相等则判断beigin和end是否相等,相等没有重复元素需要删除,不相等删除[being+1,end]中元素。
如果最后几个元素重复,则需要最后单独通过判断begin,end是否等来解决。
【代码1】
/********************************* * 日期:2014-01-28 * 作者:SJF0115 * 题号: Remove Duplicates from Sorted List II * 来源:http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ * 结果:AC * 来源:LeetCode * 总结: **********************************/ #include <iostream> #include <stdio.h> #include <algorithm> using namespace std; 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 *dummy = (ListNode*)malloc(sizeof(ListNode)); dummy->next = head; //记录上一节点的值 int preVal = head->val; ListNode *pre = head,*cur = head->next; //begin 要删除节点的上一节点 end 要删除的最后节点 ListNode *begin = dummy,*end = dummy; while(cur != NULL){ if(cur->val == preVal){ //如果当前元素和上一个元素相等则更新删除截至元素 end = cur; } else{ preVal = cur->val; //[begin,end]有重复元素 if(begin != end){ //删除重复元素 begin->next = end->next; end = begin; } //[begin,end]没有重复元素,更新删除起始元素 else{ begin = end = pre; } } pre = cur; cur = cur->next; } //如果最后几个元素相等例如:2,1,1,1,1 if(begin != end){ //删除重复元素 begin->next = end->next; } return dummy->next; } }; int main() { Solution solution; int A[] = {2,1,1,1,1,1}; ListNode *head = (ListNode*)malloc(sizeof(ListNode)); head->next = NULL; ListNode *node; ListNode *pre = head; for(int i = 0;i < 6;i++){ node = (ListNode*)malloc(sizeof(ListNode)); node->val = A[i]; node->next = NULL; pre->next = node; pre = node; } head = solution.deleteDuplicates(head->next); while(head != NULL){ printf("%d ",head->val); head = head->next; } return 0; }
【代码2】
class Solution { public: ListNode *deleteDuplicates(ListNode *head) { ListNode *dummy = (ListNode*)malloc(sizeof(ListNode)); dummy->next = head; ListNode *pre = dummy,*cur = head; while (cur != NULL) { int preVal = cur->val; if (cur->next && cur->next->val == preVal) { while (cur && cur->val == preVal) { pre->next = cur->next; delete cur; cur = pre->next; } cur = pre; } pre = cur; cur = cur->next; } return dummy->next; } };
【代码3】
class Solution { public: ListNode *deleteDuplicates(ListNode *head) { ListNode *dummy = (ListNode*)malloc(sizeof(ListNode)); dummy->next = head; ListNode *pre = dummy,*cur = head; ListNode *temp; int i = 0; while (cur != NULL) { //判断是否有重复元素 bool duplicated = false; //寻找重复元素删除 while(cur->next != NULL && (cur->val == cur->next->val)){ duplicated = true; temp = cur->next; //删除cur元素 pre->next = cur->next; cur = temp; }//while //删除重复元素的最后一个 if(duplicated){ temp = cur->next; //删除重复元素的最后一个 pre->next = cur->next; cur = temp; continue; }//if pre = cur; cur = cur->next; }//while return dummy->next; } };