题目描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

思路

方法 1

新建一个链表 newhead，第一个节点的值是 head 的值。

用两个节点 p 与 q

p 用来循环判断当前节点与下一个节点是否相等

  • 若相等的话，p 就等于 p 的下一个节点。
  • 若不相等，那么 q 的下一个节点 指向 p 的下一个节点

最后 q 所指向的节点就都不是重复的。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *p = head;
        ListNode *newhead = new ListNode(head->val);
        ListNode *q = newhead;
        while(p->next != NULL)
        {
            if(p->val == p->next->val)
            {
                p = p->next;
            }
            else
            {
                p = p->next;
                q->next = p;
                q = p;
            }
        }
        q->next = NULL;
        return newhead;

    }
};
方法 2

当 p 与 p 的下一个节点相同时，p 的 next 指向 p 的 next 的 next。

不相同时 p 就等于 p 的 next 往后移动。

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

    }
};