083-删除排序链表中的重复元素

题目描述

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

示例 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;

    }
};