leetcode[82] Remove Duplicates from Sorted List II
給定一個有序鏈表，刪除相同值的節點。例如
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
我是新建一個ans鏈表，來存鏈表中distinct的值。不知道這樣符合要求不。
判斷當前的值不等於前面一個也不等於後面一個那麼就是符合條件的節點之一。
復制代碼
/**
* 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 *ans = new ListNode(0);
ListNode *pre = ans;
ListNode *now = head->next;
ListNode *last = head;
if (now && now->val != last->val) // 第一次要先判斷，因為now從第二個節點開始
{
ListNode *tmp = new ListNode(last->val);
pre->next = tmp;
pre = pre->next;
}
while(now)
{
if ((now -> next == NULL || now->next && now->val != now->next->val) && now->val != last->val)
{
ListNode *tmp = new ListNode(now->val);
pre->next = tmp;
pre = pre->next;
now = now->next;
last = last->next;
continue;
}
now = now->next;
last = last->next;
}
head = ans->next;
delete(ans);
return head;
}
};
復制代碼
因為我是另外開辟的，所以我還看了原鏈表中操作的。這個不錯：
用pre和now去刪除節點，由於頭節點也有可能刪除，因此先建一個Head節點連頭節點。
pre從Head開始，用now去判斷是否重復。
如果重復，循環到下一個不同元素之前，把之間的相同元素直接跳過。
再向前移動pre和now指針。
復制代碼
/**
* 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 *pre,*now,*Head;
if(!head||!head->next)return head;
Head=new ListNode(-1);
Head->next=head;
pre=Head;
now=head;
while(now&&now->next)
{
if(now->val == now->next->val)
{
while(now->next && now->val == now->next->val)
{
now=now->next;
}
pre->next=now->next;
now=now->next;
}
else
{
pre=now;
now=now->next;
}
}
head=Head->next;
delete(Head);
return head;
}
};
