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

一、题目

1、题目描述

给定一个已排序的链表的头?head?，?删除所有重复的元素，使每个元素只出现一次?。返回?已排序的链表?。

2、接口描述

?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {

    }
};

3、原题链接

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

二、解题报告

1、思路分析

一次遍历，去重即可

2、复杂度

时间复杂度： O(N) 空间复杂度：O(1)

3、代码详解

?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* pre = head;
        for(auto it = head -> next ; it ; it = it -> next)
        if(it->val == pre->val) pre->next = it->next;
        else pre = it;
        return head;
    }
};