83. 删除排序链表中的重复元素

文|Seraph

01 | 问题

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

示例 1:

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

示例 2:

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

02 |解题

初解：

双指针，遇到相同的元素则越过，不同的元素则衔接。

/**
 * 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 *pre=head;
        ListNode *p=head;
        while(p)
        {
            p=p->next;
            if(p!=nullptr&&pre->val!=p->val)
            {
                pre->next=p;
                pre=pre->next;
            }
        }
        if(pre!=nullptr)
            pre->next = nullptr;
        return head;
    }
};

终解：

这里使用双while，第二个while保证向前越过所有相同的元素。有时候不要误以为两个循环就耗时就一定大于一个循环。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur = head;
        while(cur)
        {
            ListNode* next = cur->next;
            while(next && cur->val == next->val)
                next = next->next;
            cur->next = next;
            cur = next;
        }
        return head;
    }
};

03 | 积累知识点

官网链接 Leetcode No.83