220
京東網上商城
[LeetCode]82.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：
遍曆鏈表，記錄重複元素的起始位置和截止位置。要刪除的重複元素的上一個位置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
* 來源：https://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;
}
};
最後更新：2017-04-03 12:54:53