2. 从有序链表和数组中移出重复元素 Remove Duplicates

浏览数：58 / 时间：2015年06月08日

1. 链表 Remove Duplicates from Sorted List

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.

思路：
关于链表一般有两种实现方式：递归和非递归
递归实现：

    ListNode* h = head;
    if (h == NULL)
        return NULL;
    if (h->next != NULL && h->next->next != NULL && h->val == h->next->val)
        h->next = h->next->next;
    h->next = deleteDuplicates(h->next);
    return h;

因为可能对于存在连续3个以上相同元素时，对于指针的右移需要考虑更多的情况。如下的程序中，当元素1,2相等，当删除第二个元素后，指针右移，此时以第3个元素为起始递归，若第3个元素和第1个元素相等，则出错。要想正确编写，比较复杂。

非递归实现：

/**
 * 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* h = head;
        if(h == NULL)
            return NULL;
        ListNode* t = NULL;
        while (h != NULL)
        {
            t = h; //参考指针
            while ((h = h->next) != NULL ) //循环右移，直至不等
            {
                if(t->val == h->val)
                    continue;
                else
                    break;
            }
            t->next = h;
        }
        return head;
    }
};