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:
No comments:
Post a Comment