83. Remove Duplicates from Sorted List

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

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

---

删除已排序链表中的重复元素。简单，直接遍历，发现后面元素(tail)和前面元素(head)的值相同时，则删除后面元素，直到链表结束。 完整代码如下：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* new_head = head;
        ListNode *prior = head, *tail = prior->next;
        while (tail != NULL) {
            while (tail != NULL && tail->val == prior->val) {
                prior->next = tail->next;
                tail = prior->next;
            }
            if (tail == NULL)
                break;
            if (tail->val != prior->val) {
                prior = tail;
                tail = prior->next;
            }
        }
        return new_head;
    }
};

本代码提交AC，用时19MS。

下面提供一个由数组生成链表以及打印链表的函数，方便调试。

// 根据数组生成链表
ListNode* GenList(vector<int>& nums)
{
    if (nums.size() == 0)
        return NULL;
    ListNode* head = new ListNode(nums[0]);
    ListNode* tail = head;
    for (int i = 1; i < nums.size(); i++) {
        ListNode* node = new ListNode(nums[i]);
        tail->next = node;
        tail = tail->next;
    }
    return head;
}
// 打印链表
void PrintList(ListNode* head)
{
    while (head != NULL) {
        cout << head->val << endl;
        head = head->next;
    }
}

二刷。简洁代码：

class Solution {
public:
	ListNode* deleteDuplicates(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *l1 = head, *l2 = head->next;
		while (l2) {
			while (l2&&l2->val == l1->val) {
				//ListNode *tmp = l2;
				l2 = l2->next;
				//delete tmp;
			}
			l1->next = l2;
			l1 = l2;
		}
		return head;
	}
};

本代码提交AC，用时16MS。