Remove Duplicates from Linked List in Go

Program Code

package main

import "fmt"

// ListNode defines a node in a singly linked list
type ListNode struct {
    Val  int
    Next *ListNode
}

// removeDuplicates removes duplicate elements from a linked list
func removeDuplicates(head *ListNode) *ListNode {
    // Use a map to track seen values
    seen := make(map[int]bool)
    dummy := &ListNode{}
    current := dummy

    for head != nil {
        if !seen[head.Val] {
            seen[head.Val] = true
            current.Next = head
            current = current.Next
        }
        head = head.Next
    }
    // Terminate the list
    current.Next = nil

    return dummy.Next
}

// Helper function to print the linked list
func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val, " ")
        head = head.Next
    }
    fmt.Println()
}

// Main function to test the removeDuplicates function
func main() {
    // Create a linked list with duplicate elements: 1 -> 2 -> 2 -> 3 -> 4 -> 4
    head := &ListNode{1, &ListNode{2, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{4, nil}}}}}}

    fmt.Print("Original List: ")
    printList(head)

    // Remove duplicates from the linked list
    head = removeDuplicates(head)

    fmt.Print("List after removing duplicates: ")
    printList(head)
}
    

Explanation

The Go program is designed to remove duplicate elements from a singly linked list. Here is a detailed explanation of the program structure:

1. ListNode Definition

The ListNode struct defines a node in a singly linked list, containing a value (Val) and a pointer to the next node (Next).

2. removeDuplicates Function

The removeDuplicates function removes duplicate elements from a linked list:

• seen is a map used to track values that have already been encountered.
• dummy is a dummy node used to simplify list manipulation.
• current keeps track of the last node in the result list.
• The function iterates through the original list. For each node, it checks if the value is already in the seen map:
  • If the value is not in the map, it adds the value to the map and appends the node to the result list.
  • If the value is already in the map, the node is skipped.
• After the iteration, current.Next is set to nil to terminate the list.

3. printList Function

The printList function is a utility to print the elements of a linked list.

4. Main Function

The main function creates a linked list with duplicate elements, prints the original list, removes duplicates using removeDuplicates, and prints the resulting list.