El-Sam · October 13, 2017 21:18 · Oct 13, 2017
diff --git a/mergeTwoSortedLinkedLists.java b/mergeTwoSortedLinkedLists.java
@@ -0,0 +1,47 @@
+/*
+  Merge two linked lists 
+  head pointer input could be NULL as well for empty list
+  Node is defined as 
+  class Node {
+     int data;
+     Node next;
+  }
+*/
+
+Node mergeLists(Node headA, Node headB) {
+    if(headA == null && headB == null)
+        return null;
+
+    if(headA == null)
+        return headB;
+
+    if(headB == null)
+        return headA;
+
+    Node root = (headA.data < headB.data)? headA: headB;
+
+    while(headA != null && headB != null){
+
+        if(headA.data < headB.data){
+            if((headA.next == null) || (headA.next != null && headB.data < headA.next.data)){
+                Node tmp = headB.next;
+                headB.next = headA.next;
+                headA.next = headB;
+
+                headB = tmp;
+            }
+             headA = headA.next;
+        }else {
+            if((headB.next == null) || (headB.next != null && headA.data < headB.next.data)){
+                Node tmp = headA.next;
+                headA.next = headB.next;
+                headB.next = headA;
+
+                headA = tmp;
+            }
+            headB = headB.next;
+        }
+    }
+
+    return root;
+}
No results found