Fix singly linked list (TheAlgorithms#2988)

funCodeSonali · web-flow · commit 77bcd4daa3c9 · 2022-04-03T16:11:43.000+03:00
diff --git a/pom.xml b/pom.xml
@@ -43,6 +43,14 @@
                 <artifactId>maven-surefire-plugin</artifactId>
                 <version>2.22.2</version>
             </plugin>
+            <plugin>
+                <groupId>org.apache.maven.plugins</groupId>
+                <artifactId>maven-compiler-plugin</artifactId>
+                <configuration>
+                    <source>16</source>
+                    <target>16</target>
+                </configuration>
+            </plugin>
         </plugins>
     </build>
 </project>
diff --git a/src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java b/src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java
@@ -44,16 +44,14 @@ public SinglyLinkedList(Node head, int size) {
     public boolean detectLoop() {
         Node currentNodeFast = head;
         Node currentNodeSlow = head;
-        boolean flag = false;
-        while (currentNodeFast != null && currentNodeFast.next != null && currentNodeSlow != null && currentNodeSlow.next != null) {
+        while (currentNodeFast != null && currentNodeFast.next != null) {
             currentNodeFast = currentNodeFast.next.next;
             currentNodeSlow = currentNodeSlow.next;
             if (currentNodeFast == currentNodeSlow) {
-                flag = true;
-                break;
+                return true;
             }
         }
-        return flag;
+        return false;
     }
 
     /**
@@ -84,7 +82,7 @@ public void swapNodes(int valueFirst, int valueSecond) {
         if(previousA != null){
             previousA.next = currentB;
         }
-        else{ 
+        else{
             // make 'b' as the new head
             head = currentB;
         }
@@ -98,7 +96,7 @@ public void swapNodes(int valueFirst, int valueSecond) {
             head = currentA;
         }
         // Swap next pointer
-        
+
         Node temp = currentA.next;
         currentA.next = currentB.next;
         currentB.next = temp;
@@ -109,15 +107,19 @@ public void swapNodes(int valueFirst, int valueSecond) {
      *
      */
     Node reverseList(Node node) {
+        Node prevNode = head;
+        while(prevNode.next!=node){
+            prevNode = prevNode.next;
+        }
         Node prev = null, curr = node, next;
         while (curr != null) {
             next = curr.next;
             curr.next = prev;
             prev = curr;
             curr = next;
         }
-        node = prev;
-        return node;
+        prevNode.next = prev;
+        return head;
     }
 
     /**
@@ -161,6 +163,14 @@ public Node getHead() {
         return head;
     }
 
+    /**
+     * Set head of the list.
+     *
+     */
+    public void setHead(Node head) {
+        this.head = head;
+    }
+
     /**
      * Calculate the count of the list manually
      *
@@ -205,145 +215,41 @@ public String toString() {
         return joiner.toString();
     }
 
-    /**
-     * Driver Code
-     */
-    public static void main(String[] arg) {
-        SinglyLinkedList list = new SinglyLinkedList();
-        assert list.isEmpty();
-        assert list.size() == 0 && list.count() == 0;
-        assert list.toString().equals("");
-
-        /* Test insert function */
-        list.insertHead(5);
-        list.insertHead(7);
-        list.insertHead(10);
-        list.insert(3);
-        list.insertNth(1, 4);
-        assert list.toString().equals("10->7->5->3->1");
-
-        /* Test search function */
-        assert list.search(10) && list.search(5) && list.search(1) && !list.search(100);
-
-        /* Test get function */
-        assert list.getNth(0) == 10 && list.getNth(2) == 5 && list.getNth(4) == 1;
-
-        /* Test delete function */
-        list.deleteHead();
-        list.deleteNth(1);
-        list.delete();
-        assert list.toString().equals("7->3");
-
-        assert list.size == 2 && list.size() == list.count();
-
-        list.clear();
-        assert list.isEmpty();
-
-        try {
-            list.delete();
-            assert false;
-            /* this should not happen */
-        } catch (Exception e) {
-            assert true;
-            /* this should happen */
-        }
-
-        Node instance = new Node();
-        Node head = new Node(0, new Node(2, new Node(3, new Node(3, new Node(4)))));
-        head = instance.deleteDuplicates(head);
-        instance.print(head);
-
-    }
-}
-
-/**
- * This class is the nodes of the SinglyLinked List. They consist of a value and
- * a pointer to the node after them.
- */
-class Node {
-
-    /**
-     * Head refer to the front of the list
-     */
-    public Node head;
-
-    /**
-     * Size of SinglyLinkedList
-     */
-    public int size;
-
-
-
-    /**
-     * The value of the node
-     */
-    int value;
-
-    /**
-     * Point to the next node
-     */
-    Node next;
-
-    Node() {
-    }
-
-    /**
-     * Constructor
-     *
-     * @param value Value to be put in the node
-     */
-    Node(int value) {
-        this(value, null);
-    }
+    public void deleteDuplicates() {
 
-    /**
-     * Constructor
-     *
-     * @param value Value to be put in the node
-     * @param next Reference to the next node
-     */
-    Node(int value, Node next) {
-        this.value = value;
-        this.next = next;
-    }
-
-    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) {
+        Node pred = head;
+        // predecessor = the node
+        // having sublist of its duplicates
+        Node newHead = head;
+        while (newHead != null) {
             // if it's a beginning of duplicates sublist
             // skip all duplicates
-            if (head.next != null && head.value == head.next.value) {
+            if (newHead.next != null && newHead.value == newHead.next.value) {
                 // move till the end of duplicates sublist
-                while (head.next != null && head.value == head.next.value) {
-                    head = head.next;
+                while (newHead.next != null && newHead.value == newHead.next.value) {
+                    newHead = newHead.next;
                 }
                 // skip all duplicates
-                pred.next = head.next;
+                pred.next = newHead.next;
+                newHead = null;
+
                 // otherwise, move predecessor
-            } else {
-                pred = pred.next;
             }
-
             // move forward
-            head = head.next;
+            pred = pred.next;
+            newHead = pred;
         }
-        return sentinel.next;
     }
 
-    public void print(Node head) {
+    public void print() {
         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);
+            System.out.println();
         }
     }
 
@@ -379,39 +285,29 @@ public void insertNth(int data, int position) {
             head = newNode;
             size++;
             return;
-        } else if (position == 0) {
+        }
+        if (position == 0) {
             /* insert at the head of the list */
             newNode.next = head;
             head = newNode;
             size++;
             return;
         }
+
         Node cur = head;
         for (int i = 0; i < position - 1; ++i) {
             cur = cur.next;
         }
         newNode.next = cur.next;
         cur.next = newNode;
         size++;
+
     }
 
     /**
      * Swaps nodes of two given values a and b.
      *
      */
-    public void swapNodes(int a, int b) {
-        Node currentNode = head;
-        Node temp = null;
-        while (currentNode != null) {
-            if (currentNode.next.value == a) {
-                temp = currentNode.next;
-            }
-            if (currentNode.next.value == b) {
-                currentNode.next = temp;
-            }
-            currentNode = currentNode.next;
-        }
-    }
 
     /**
      * Deletes a node at the head
@@ -479,4 +375,96 @@ public void checkBounds(int position, int low, int high) {
             throw new IndexOutOfBoundsException(position + "");
         }
     }
+    /**
+     * Driver Code
+     */
+    public static void main(String[] arg) {
+        SinglyLinkedList list = new SinglyLinkedList();
+        assert list.isEmpty();
+        assert list.size() == 0 && list.count() == 0;
+        assert list.toString().equals("");
+
+        /* Test insert function */
+        list.insertHead(5);
+        list.insertHead(7);
+        list.insertHead(10);
+        list.insert(3);
+        list.insertNth(1, 4);
+        assert list.toString().equals("10->7->5->3->1");
+        System.out.println(list.toString());
+        /* Test search function */
+        assert list.search(10) && list.search(5) && list.search(1) && !list.search(100);
+
+        /* Test get function */
+        assert list.getNth(0) == 10 && list.getNth(2) == 5 && list.getNth(4) == 1;
+
+        /* Test delete function */
+        list.deleteHead();
+        list.deleteNth(1);
+        list.delete();
+        assert list.toString().equals("7->3");
+        System.out.println(list.toString());
+        assert list.size == 2 && list.size() == list.count();
+
+        list.clear();
+        assert list.isEmpty();
+
+        try {
+            list.delete();
+            assert false;
+            /* this should not happen */
+        } catch (Exception e) {
+            assert true;
+            /* this should happen */
+        }
+
+        SinglyLinkedList instance = new SinglyLinkedList();
+        Node head = new Node(0, new Node(2, new Node(3, new Node(3, new Node(4)))));
+        instance.setHead(head);
+        instance.deleteDuplicates();
+        instance.print();
+
+    }
+
+}
+
+/**
+ * This class is the nodes of the SinglyLinked List. They consist of a value and
+ * a pointer to the node after them.
+ */
+class Node {
+
+    /**
+     * The value of the node
+     */
+    int value;
+
+    /**
+     * Point to the next node
+     */
+    Node next;
+
+    Node() {
+    }
+
+    /**
+     * Constructor
+     *
+     * @param value Value to be put in the node
+     */
+    Node(int value) {
+        this(value, null);
+    }
+
+    /**
+     * Constructor
+     *
+     * @param value Value to be put in the node
+     * @param next Reference to the next node
+     */
+    Node(int value, Node next) {
+        this.value = value;
+        this.next = next;
+    }
+
 }
