LeetCode 83 Remove Duplicates from Sorted List（從已排序連結清單中移除重複元素）（Linked List）（*）

版權聲明：轉載請聯系本人，感謝配合！本站位址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50514648

翻譯

給定一個已排序連結清單，删除所有重複元素讓每個元素隻出現一次。

例如：
給定 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.           

分析

大家可以先看看這篇部落格：

LeetCode 206 Reverse Linked List（反轉連結清單）（四步将遞歸改寫成疊代）（*）

，然後再回過來看，因為這一篇中我用作圖的方式解釋了針對反轉連結清單的一系列過程，本題也是大同小異的。

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

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;           

代碼

C Plus Plus

/**
* 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;
    }
};           

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode c = head;
        while (c.next != null) {
            if (c.val == c.next.val) {
                c.next = c.next.next;
            } else {
                c = c.next;
            }
        }
        return c;
    }
}