LeetCode 83 Remove Duplicates from Sorted List（從已排序鏈表中移除重復元素）（*）

LeetCode 83 Remove Duplicates from Sorted List（從已排序鏈表中移除重復元素）（*）

翻譯

給定一個已排序鏈表，刪除所有重復元素讓每個元素只出現一次。

例如：
給定 1->1->2， 返回 1->2。
給定 1->1->2->3->3， 返回 1->2->3。

原文

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

分析

切入正題，首先我們應該先判斷是否為空：

if (head == NULL) return NULL;
if (head->next == NULL) return head;    

但是這兩行代碼是可以簡寫的：

if (head == NULL || head->next == NULL) return head;

下面是一個循環語句：

while (head->next) {
    if (head->val == head->next->val) {
        head->next = head->next->next;
    }
    else {
        head = head->next;
    }   
}    

意思非常簡單，首先判斷當前的節點的值與下一個節點的值是否相等，如果相等，則將下下一個節點賦值給下一個節點。

1——1——2——3——3
改寫成：
1——2——3——3

此時head還在1上，但為什麼不將其移動到2上呢，也就是說代碼為什麼不是這樣的：

while (head->next) {
    if (head->val == head->next->val) {
        head->next = head->next->next;
        head = head->next;
    }
    else {
        head = head->next;
    }   
}    

理由很簡單，例如：

1——1——1——2——3——3
經過第一次變換後：
1——1——2——3——3
如果貿然將head移動到下一個節點上，那麼下一次的對比就是對比1和2了，顯然是不合理的。

到了這裡移除操作就已經完成了，但是能夠直接returnhead嗎，顯然也是不能的，因為head已經移動到了最後一個節點了。

所以應該在while循環之前就設置了新的head作為記錄，最後返回它就好了。

ListNode* newHead = head;
while(){}
return newHead;

代碼

/**
* 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* newNode = head;
        while (head->next) {
            if (head->val == head->next->val)
                head->next = head->next->next;
            else
                head = head->next;
        }
        return newNode;
    }
};