</>Ali · LeetCode
#0083·EasyLinked Lists

Remove Duplicates from Sorted List

LeetCode #83 · Easy · Linked Lists · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Linear Traversal

Strategy

  1. 1Traverse the list using a pointer `tmp`.
  2. 2Compare the current node's value with the next node's value.
  3. 3If they are the same, bypass the next node (delete duplicate).
  4. 4If they are different, move the pointer forward.
Time
O(n)
Space
O(1)
Problem description(from LeetCode)

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Examples

Example 1
Input:
head = [1,1,2]
Output:
[1,2]

Constraints

  • •The number of nodes in the list is in the range [0, 300].
  • •-100 <= Node.val <= 100
  • •The list is guaranteed to be sorted in ascending order.

C++ Solution

solution.cpp
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 == nullptr || head->next == nullptr) return head;
    ListNode *tmp = head;
    ListNode *tmpNext = head->next;
    while (tmpNext != nullptr) {
      if (tmp->val == tmpNext->val) {
        tmp->next = tmpNext->next;
        tmpNext = tmpNext->next;
      } else {
        tmp = tmp->next;
        tmpNext = tmpNext->next;
      }
    }

    return head;
  }
};

More Linked Lists problems