Add remove duplicate nodes from a sorted linked list algorithm (TheAlgorithms#2452)

ranjan-mohanty · web-flow · commit 4d06c5f6ba8a · 2021-10-12T08:19:21.000+03:00
diff --git a/DataStructures/Lists/RemoveDuplicateNodes.java b/DataStructures/Lists/RemoveDuplicateNodes.java
@@ -0,0 +1,53 @@
+package DataStructures.Lists;
+
+import DataStructures.Lists.Node;
+
+public class RemoveDuplicateNodes {
+
+    public Node deleteDuplicates(Node head) {
+        // sentinel
+        Node sentinel = new Node(0, head);
+
+        // predecessor = the last node 
+        // before the sublist of duplicates
+        Node pred = sentinel;
+
+        while (head != null) {
+            // if it's a beginning of duplicates sublist 
+            // skip all duplicates
+            if (head.next != null && head.value == head.next.value) {
+                // move till the end of duplicates sublist
+                while (head.next != null && head.value == head.next.value) {
+                    head = head.next;
+                }
+                // skip all duplicates
+                pred.next = head.next;
+                // otherwise, move predecessor
+            } else {
+                pred = pred.next;
+            }
+
+            // move forward
+            head = head.next;
+        }
+        return sentinel.next;
+    }
+
+    public void print(Node head) {
+        Node temp = head;
+        while (temp != null && temp.next != null) {
+            System.out.print(temp.value + "->");
+            temp = temp.next;
+        }
+        if (temp != null) {
+            System.out.print(temp.value);
+        }
+    }
+
+    public static void main(String arg[]) {
+        RemoveDuplicateNodes instance = new RemoveDuplicateNodes();
+        Node head = new Node(0, new Node(2, new Node(3, new Node(3, new Node(4)))));
+        head = instance.deleteDuplicates(head);
+        instance.print(head);
+    }
+}
