12. Remove Consecutive Duplicates from Sorted Linked List

Origin: Remove Consecutive Duplicates from Sorted Linked List

Write a function “deleteDuplicates” that removes consecutive duplicate nodes in-place, retaining only the first node of each value. Return the head of the resulting list.

Example

Input: head = [1, 2, 2, 2, 3, 4, 4, 5]

Output: [1, 2, 3, 4, 5]

Explanation: Given 1→2→2→2→3→4→4→5. Start at 1 (next is 2, no skip). Move to 2; skip all consecutive 2’s so that 2 links directly to 3 (removing two extra 2 nodes). Now list is 1→2→3→4→4→5. Move to 3 (next is 4, no skip). At 4, skip the duplicate 4 so it links to 5. The resulting list is 1→2→3→4→5.

Input Format

• The first line n contains the length of the linked list
• The next n lines contains the elements of the linked list

Example:

8
1 2 2 2 3 4 4 5

here 8 is the length of the linked list followed by the nodes of the list.

Constraints

• 0 <= n <= 1000, where n is the number of nodes in the linked list
• -10^5 <= Node.val <= 10^5 for each node in the list
• The linked list is sorted in non-decreasing order: for each node u with successor v, u.val <= v.val

Output Format

• The function returns one value: the head of the deduplicated list

Sample Input 0

0

Sample Input 1

1
1

Sample Output 1

1

---

函数契约

// 输入：head（有序链表的头节点）
// 输出：去重后链表的头节点
// 边界：head = null → null；单节点 → 原样返回；全部相同 → 只剩一个节点

边界表

场景	返回什么
head = null	null
单节点	head（原样）
全部相同值	只保留一个节点
无重复	head（原样）
正常场景	去重后的 head

Resolution

我的解法

function deleteDuplicates(head: SinglyLinkedListNode): SinglyLinkedListNode {
    if (!head) return head
    let fast: SinglyLinkedListNode = head.next!
    let slow: SinglyLinkedListNode = head
 
    while (fast) {
        if (fast?.data === slow.data) {
            while (fast?.data === slow.data) {
                fast = fast.next!
            }
            slow.next = fast
        }
        fast = fast?.next!
        slow = slow.next!
    }
    return head
}

解题思路

快慢指针，fast 负责跳过重复节点，slow 负责重新连接。

遍历过程：

1. fast 和 slow 同时出发，fast 在 slow 的下一个节点
2. 如果 fast.data === slow.data，内层 while 让 fast 一直跳过重复节点，直到找到不同的，然后 slow.next = fast 把重复的节点全部跳过
3. fast 和 slow 各前进一步

链表已排序，所以重复值一定相邻，不需要额外数据结构。

复杂度

• 时间：O(n)，每个节点最多被访问一次
• 空间：O(1)，两个指针

测试用例

输入	输出	场景
[1, 2, 2, 3, 3, 4]	[1, 2, 3, 4]	正常去重
[1]	[1]	单节点
[1, 1, 1, 1, 1]	[1]	全部相同
[1, 1, 1, 2, 2, 2, 3, 3, 3]	[1, 2, 3]	多组连续重复
[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5]	无重复
[]	[]	空链表
[1, 1, 2, 2, 2, 3, 4, 4, 5]	[1, 2, 3, 4, 5]	题目示例
[1, 1, 1]	[1]	末尾重复到尾部

全部通过。

参考来源

• 相关文章：链表解题
• 相关文章：算法解题流程：从读题到提交的七步