Remove Duplicate from unsorted Linked List in Kotlin

To remove a duplicate from an unsorted linked list, you can follow these steps:

1. Traverse the linked list and keep track of each element’s frequency. You can use a hash table to store the frequency of each element.
2. Traverse the linked list again, and for each element, check its frequency in the hash table. If the frequency is greater than one, remove that element from the linked list.

class Node(var data: Int) {
    var next: Node? = null
}

fun removeDuplicates(head: Node?) {
    val freq = mutableMapOf<Int, Int>()
    var current: Node? = head
    var prev: Node? = null

    while (current != null) {
        if (freq.containsKey(current.data)) {
            prev?.next = current.next // Remove duplicate
        } else {
            freq[current.data] = 1
            prev = current
        }
        current = current.next
    }
}

// Example usage
fun main() {
    // Create a linked list with duplicates
    val head = Node(1)
    head.next = Node(2)
    head.next?.next = Node(3)
    head.next?.next?.next = Node(2)
    head.next?.next?.next?.next = Node(4)

    // Call removeDuplicates function to remove duplicates
    removeDuplicates(head)

    // Print the linked list
    print("${head.data} ")
    var current = head.next
    while (current != null) {
        print("${current.data} ")
        current = current.next
    }
}

1. The Node class is defined to represent a node in the linked list. It has a constructor that takes an integer value and initializes the data property, and a nullable next property that points to the next node in the list.
2. The removeDuplicates function takes the head of the linked list as a parameter and removes duplicates from it. It first creates a mutable map freq to keep track of the frequency of each element in the linked list.
3. The function initializes two variables current and prev to traverse the linked list. current starts from the head of the list, and prev initially points to null.
4. The function uses a while loop to iterate through the linked list. Inside the loop, it checks if the current node’s data is already present in the freq map using the containsKey method. If it is, then it means the current node is a duplicate, and the function removes it by updating the next property of the previous node to point to the next node of the current node, effectively skipping over the current node. If the current node’s data is not present in the freq map, then it means the node is not a duplicate, and the function adds it to the freq map and updates the prev variable to point to the current node.
5. The main function creates a linked list with duplicates, calls the removeDuplicates function to remove duplicates, and then iterates through the linked list to print its elements.

The output of the program will be: 1 2 3 4, which is the linked list with duplicates removed.