Delete Duplicate Nodes in a Linked List

1. Problem Description

In a sorted linked list, duplicate nodes may exist. Delete all duplicate nodes from the list without retaining any duplicate occurrence, and return the head pointer. For example, 1->2->3->3->4->4->5 becomes 1->2->5.

2. Approach

Traverse the list to find duplicate nodes and store them in a set, then traverse again and delete nodes whose values are in the set.

3. Implementation

• java

public class 删除链表中重复的结点
{
    public ListNode deleteDuplication(ListNode pHead)
    {
        // Check parameters
        if (pHead == null)
        {
            return null;
        }
        // Traverse the list; if the current node equals the next node, it is duplicated, so add it to the set
        ListNode current = pHead;
        Set<Integer> set = new HashSet<>();
        while (current != null)
        {
            if (current.next != null && current.val == current.next.val)
            {
                set.add(current.val);
            }
            current = current.next;
        }
        // Traverse the list again; if a node is in the set, delete it
        ListNode newHead = pHead;
        current = newHead;
        while (current != null)
        {
            if (current.next != null &&
                    set.contains(current.next.val))
            {
                current.next = current.next.next;
                continue;
            }
            current = current.next;
        }

        // The head node may also be duplicated
        if (set.contains(newHead.val))
        {
            newHead = newHead.next;
        }
        return newHead;
    }
}

• go

// Space: O(n)
// Time: O(n)
func deleteDuplication(pHead *ListNode) *ListNode {

	if pHead == nil {
		return nil
	}

	countMap := make(map[int]int)
	n := pHead
	for n != nil {
		countMap[n.Val] = countMap[n.Val] + 1
		n = n.Next
	}

	n = pHead.Next
	newHead := pHead
	newN := newHead
	for n != nil {
		if countMap[n.Val] == 1 {
			newN.Next = n
			newN = newN.Next
		}
		n = n.Next
	}

	newN.Next = nil
	if countMap[newHead.Val] > 1 {
		return newHead.Next
	}
	return newHead
}

func deleteDuplication(pHead *ListNode) *ListNode {
	if pHead == nil {
		return nil
	}

	count := make(map[int]int, 0)
	h := pHead
	for h != nil {
		count[h.Val]++
		h = h.Next
	}

	dummyHead := &ListNode{
		Val:  0,
		Next: pHead,
	}

	// Use two pointers for deletion
	prev := dummyHead
	current := prev.Next
	for current != nil {
		// The next one may also be duplicated, so prev does not need to be updated
		if count[current.Val] > 1 {
			prev.Next = current.Next
		} else {
			prev = current
		}
		current = current.Next

	}

	return dummyHead.Next
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeDuplicateNodes(head *ListNode) *ListNode {
    m := make(map[int]bool, 0)
    dummyHead := &ListNode{}
    d := dummyHead
    current := head
    var next *ListNode
    for current != nil {
        // Save the next pointer first, then clear it to avoid affecting later operations
        next = current.Next
        current.Next = nil
        if !m[current.Val] {
            d.Next = current
            d = d.Next
            m[current.Val] = true
        }
        current = next
    }
    return dummyHead.Next
}

4. References

• Delete Duplicate Nodes from a Linked List - NowCoder
• Interview Question 02.01. Remove Duplicate Node - LeetCode
• 82. Remove Duplicates from Sorted List II - LeetCode