Home > Software design >  Removing Duplicates from a Linked List?
Removing Duplicates from a Linked List?

Time:12-01

Hello I was doing an algorithm problem where you remove duplicates from a SORTED linked List

and this is what I have :

function removeDuplicatesFromLinkedList(linkedList) {
    let currentNode = linkedList;
    console.log('currentNode', currentNode)
    while (currentNode) {
        let nextDifferentNode = currentNode.next;
        console.log('assignment', nextDifferentNode)
        while (nextDifferentNode && nextDifferentNode.value === currentNode.value) {
            nextDifferentNode = nextDifferentNode.next
                    console.log('nextDifferentNode', nextDifferentNode)
        }
        currentNode.next = nextDifferentNode
        currentNode = nextDifferentNode
    }
  return linkedList

}

the argument parameter linkedList refers to the head node and its next value. I was wondering why we are returning linkedList at the end, does this mean we mutated the .next properties of the original linkedList nodes?

CodePudding user response:

A LinkedList is like node1 -> node2 -> node3 -> ..... null. The input parameter, linkedList is the head of the linked list. The node1 in my example. While we mutate the list we want to return the head at the end, which unfortunately is named linkedList here.

To clear that we are going to change the name of the input parameter to the function. We name it head because its really just the head of the linked list while the linked list is the whole data structure. As we move forward we mutate the next pointers as needed to drop duplicate nodes.

function removeDuplicatesFromLinkedList(head) {
    let currentNode = head;
    console.log('currentNode', currentNode)
    while (currentNode) {
        let nextDifferentNode = currentNode.next;
        console.log('assignment', nextDifferentNode)
        while (nextDifferentNode && nextDifferentNode.value === currentNode.value) {
            nextDifferentNode = nextDifferentNode.next
                    console.log('nextDifferentNode', nextDifferentNode)
        }
        currentNode.next = nextDifferentNode
        currentNode = nextDifferentNode
    }
  return head

As you can see we receive the head, assign it to a variable that we are change on work on and keep head to return at the end.

  • Related