Merge two sorted linked lists

public class MergeLinkedLists {

static class ListNode {

int val;

ListNode next;

public ListNode() {}

public ListNode(int val) {

this.val = val;

}

public ListNode(int val, ListNode next) {

this.val = val;

this.next = next;

}

}

public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {

ListNode mergedList = new ListNode();

ListNode current = mergedList;

while (list1 != null && list2 != null) {

if (list1.val <= list2.val) {

current.next = list1;

list1 = list1.next;

} else {

current.next = list2;

list2 = list2.next;

}

current = current.next;

}

if (list1 != null) {

current.next = list1;

} else {

current.next = list2;

}

return mergedList.next;

}

public static void main(String[] args) {

// Example usage:

ListNode list1 = new ListNode(1, new ListNode(2, new ListNode(4)));

ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));

ListNode mergedList = mergeTwoLists(list1, list2);

while (mergedList != null) {

System.out.print(mergedList.val + " ");

mergedList = mergedList.next;

}

}

}

Time Complexity: O(M + N), Where M and N are the size of the list1 and list2 respectively.
Auxiliary Space: O(M+N), Function call stack space

Output:

1 1 2 3 4 4

Geeks link:

    Merge To Linked List