LeetCode 83 Remove Duplicates from Sorted List（从已排序链表中移除重复元素）（Linked 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.

分析

大家可以先看看这篇博客：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;
    }
}