Wednesday, January 17, 2024

Merge two sorted linked lists


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


No comments:

Post a Comment

Create a Digital Clock using HTML and JavaScript

Create a Digital Clock using HTML and JavaScript  <! DOCTYPE html> < html > < head > <...

Followers

Search This Blog

Popular Posts