83. Remove Duplicates from Sorted List

LeetCode 83. Remove Duplicates from Sorted List****

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.

Tags

Linked List

Solution

Traverse the linked list with two pointers pre and cur who start from head. We move cur forwardly until pre.Val != cur.Val, or cur reaches the end. Then connect pre.Next to cur. Repeat this until pre is null. Return the head at last.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$

Code

// code here.
type ListNode struct {
	Val  int
	Next *ListNode
}

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	for p := head; p != nil; p = p.Next {
		q := p.Next
		for q != nil && p.Val == q.Val {
			q = q.Next
		}
		p.Next = q
	}
	return head
}