Remove Duplicates from Sorted List

LeetCode 83 | Difficulty: Easy

Easy

Problem Description

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.

Example 1:

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

Example 2:

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

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.

Topics: Linked List

---

Approach

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 162 ms)

Metric	Value
Runtime	162 ms
Memory	N/A
Date	2017-09-20

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
                if (head == null || head.next == null) return head;
        ListNode temp = head;
        ListNode dummy = new ListNode(Int32.MinValue);
        dummy.next = head;
        ListNode prev = dummy;
        while (temp != null && temp.next != null)
        {
            if (temp.val == temp.next.val)
            {
                var first = temp;
                var data = temp.val;
                while (temp != null && temp.val == data) { temp = temp.next; }
                //connect the first node in the dup range to the next non-dup
                first.next = temp;
                prev.next = first;
                prev = first;
            }
            else
            {
                prev.next = temp;
                //update previous in case of no dupes
                prev = temp;
                if (temp != null) temp = temp.next;
            }

        }
        return dummy.next;
    }
}

---

Complexity Analysis

Approach	Time	Space
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.