Remove Duplicates from Sorted List II

时间：2014-08-23 14:00:40 收藏：0 阅读：215

Remove Duplicates from Sorted List II

Total Accepted: 17137 Total Submissions: 69046My Submissions

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

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

经典的链表题，在排好序的链表中去掉所有重复的数字，因为已经排好序，重复的数字都在一起，因此在扫描链表时把重复的删除，不重复的加到新链表即可。

/**
 * 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 *new_head, *curr_node, *next_node, *next2_node, *new_list_tail;
        curr_node = head;
        new_head = NULL;
        bool is_duplicate;
        while (curr_node) {
            next_node = curr_node->next;
            is_duplicate = false;
            while (next_node && next_node->val == curr_node->val) {
                next2_node = next_node->next;
                delete next_node;
                next_node = next2_node;
                is_duplicate = true;
            }
            if (is_duplicate) {
                delete curr_node;
            } else {
                if (NULL == new_head) {
                    new_head = curr_node;
                    new_list_tail = new_head;
                } else {
                    new_list_tail->next = curr_node;
                    new_list_tail = curr_node;
                }
            }
            curr_node = next_node;
        }
        if (new_head) {
            new_list_tail->next = NULL;
        }
        return new_head;
    }
};

原文：http://blog.csdn.net/freeliao/article/details/38777959