CODEWITHSUNDEEP
algorithmdata-structureslinked-listsingly-linked-list
Spring boot progammer
Spring boot progammer

Reputation: 157

Deletion of duplicate node in Linked List

Program to delete all the occurence of duplicate nodes from the linked list is written below. In the code, we are return new head of linked list after deletion as "dummy.next" but in starting dummy is pointing towards head so if we delete head, then dummy.next should also return the deleted node then why is it returning the new head? Example input : 1 1 1 2 3 Output:2 3

class Solution {
public ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode n = dummy;
    while (n.next != null && n.next.next != null) {
        if (n.next.val == n.next.next.val) {
            int duplicate = n.next.val;
            while (n.next != null && n.next.val == duplicate) {
                n.next = n.next.next;
            }
        } else {
            n = n.next;
        }
    }
    return dummy.next;
}

}

P.S- I do not want to return the deleted node, I want to return the new head and I just want to understand the logic behind this.

Upvotes: 0

Views: 95

Answers (2)

Jayesh Tanna
Jayesh Tanna

Reputation: 418

Remove Duplicate Nodes From Unsorted List: https://github.com/jayesh-tanna/coding-problem-solution/blob/master/DataStructures/SinglyLinkList/RemoveDuplicateNodesFromUnsortedList.java

Remove Duplicates From Sorted List: https://github.com/jayesh-tanna/coding-problem-solution/blob/master/DataStructures/SinglyLinkList/RemoveDuplicatesFromSortedList.java

Upvotes: 0

jigsawmnc
jigsawmnc

Reputation: 444

Work with a simpler example and you'll understand. Consider a list with just 2 nodes.

1  -> 1*
^
Head

(* is to denote visual distinction)

You create a new dummy node and point its next to Head

0  ->  1  ->  1*
^      ^
dummy  Head

Then, you start your iteration from dummy (by doing n = dummy)

0    ->  1  ->  1*
^        ^    
n,dummy  Head

You enter the loop and you enter the if condition. The fact that you're changing n's next, also changes dummy's next.

0    ->  1*  <- 1
^               ^
n,dummy         Head

In this way, you keep moving dummy's next as long as the consecutive values are same. Once you encounter a different value, then you march n forward and leave dummy.next pointing to the head.

Upvotes: 0

Related Questions