upate SinglyLinkedList

realDuYuanChao · realDuYuanChao · commit b54983f5bc68 · 2019-10-25T11:59:53.000+08:00
diff --git a/DataStructures/Lists/SinglyLinkedList.java b/DataStructures/Lists/SinglyLinkedList.java
@@ -30,6 +30,17 @@ public SinglyLinkedList() {
         size = 0;
     }
 
+    /**
+     * Init SinglyLinkedList with specified head node and size
+     *
+     * @param head the head node of list
+     * @param size the size of list
+     */
+    public SinglyLinkedList(Node head, int size) {
+        this.head = head;
+        this.size = size;
+    }
+
     /**
      * This method inserts an element at the head
      *
@@ -66,6 +77,23 @@ public void insertNth(int data, int position) {
         size++;
     }
 
+    /**
+     * Insert element to list, always sorted
+     *
+     * @param data to be inserted
+     */
+    public void insertSorted(int data) {
+        Node cur = head;
+        while (cur.next != null && data > cur.next.value) {
+            cur = cur.next;
+        }
+
+        Node newNode = new Node(data);
+        newNode.next = cur.next;
+        cur.next = newNode;
+        size++;
+    }
+
     /**
      * This method deletes an element at the head
      *
@@ -142,7 +170,7 @@ public boolean isEmpty() {
     /**
      * Returns the size of the linked list
      */
-    public int getSize() {
+    public int size() {
         return size;
     }
 
@@ -160,38 +188,78 @@ public String toString() {
         return builder.replace(builder.length() - 2, builder.length(), "").toString();
     }
 
+    /**
+     * Merge two sorted SingleLinkedList
+     *
+     * @param listA the first sorted list
+     * @param listB the second sored list
+     * @return merged sorted list
+     */
+    public static SinglyLinkedList merge(SinglyLinkedList listA, SinglyLinkedList listB) {
+        Node headA = listA.head.next;
+        Node headB = listB.head.next;
+
+        int size = listA.size() + listB.size();
+
+        Node head = new Node();
+        Node tail = head;
+        while (headA != null && headB != null) {
+            if (headA.value <= headB.value) {
+                tail.next = headA;
+                headA = headA.next;
+            } else {
+                tail.next = headB;
+                headB = headB.next;
+            }
+            tail = tail.next;
+        }
+        if (headA == null) {
+            tail.next = headB;
+        }
+        if (headB == null) {
+            tail.next = headA;
+        }
+        return new SinglyLinkedList(head, size);
+    }
+
     /**
      * Main method
      *
      * @param args Command line arguments
      */
     public static void main(String args[]) {
         SinglyLinkedList myList = new SinglyLinkedList();
-
         assert myList.isEmpty();
+        assert myList.toString().equals("");
 
         myList.insertHead(5);
         myList.insertHead(7);
         myList.insertHead(10);
-
-        System.out.println(myList);; // 10 -> 7 -> 5
+        assert myList.toString().equals("10->7->5");
 
         myList.deleteHead();
-
-        System.out.println(myList);; // 7 -> 5
+        assert myList.toString().equals("7->5");
 
         myList.insertNth(11, 2);
-
-        System.out.println(myList);; // 7 -> 5 -> 11
+        assert myList.toString().equals("7->5->11");
 
         myList.deleteNth(1);
-
-        System.out.println(myList);; // 7-> 11
+        assert myList.toString().equals("7->11");
 
         myList.clear();
         assert myList.isEmpty();
 
-        System.out.println(myList); // ""
+        /* Test MergeTwoSortedLinkedList */
+        SinglyLinkedList listA = new SinglyLinkedList();
+        SinglyLinkedList listB = new SinglyLinkedList();
+
+        for (int i = 10; i >= 2; i -= 2) {
+            listA.insertSorted(i);
+            listB.insertSorted(i - 1);
+        }
+        assert listA.toString().equals("2->4->6->8->10");
+        assert listB.toString().equals("1->3->5->7->9");
+        assert SinglyLinkedList.merge(listA, listB).toString().equals("1->2->3->4->5->6->7->8->9->10");
 
     }
 }
@@ -212,13 +280,21 @@ class Node {
      */
     Node next;
 
+    Node() {
+
+    }
+
     /**
      * Constructor
      *
      * @param value Value to be put in the node
      */
     Node(int value) {
+        this(value, null);
+    }
+
+    Node(int value, Node next) {
         this.value = value;
-        this.next = null;
+        this.next = next;
     }
 }
