Merge two sorted lists python

Merge Two Sorted Lists – Leetcode Solution

In this post, we are going to solve the 21. Merge Two Sorted Lists problem of Leetcode. This problem 21. Merge Two Sorted Lists is a Leetcode easy level problem. Let’s see the code, 21. Merge Two Sorted Lists – Leetcode Solution.

Problem

You are given the heads of two sorted linked lists list1 and list2 .

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1 :

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2 :

Input: list1 = [], list2 = [] Output: []

Example 3 :

Input: list1 = [], list2 = [0] Output: [0]

Constraints

Now, let’s see the code of 21. Merge Two Sorted Lists – Leetcode Solution.

Merge Two Sorted Lists – Leetcode Solution

21. Merge Two Sorted Lists – Solution in Java

This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in Java Programming Language.

/** * Definition for singly-linked list. * public class ListNode < * int val; * ListNode next; * ListNode() <>* ListNode(int val) < this.val = val; >* ListNode(int val, ListNode next) < this.val = val; this.next = next; >* > */ public class Solution < public ListNode mergeTwoLists(ListNode l1, ListNode l2) < ListNode head = new ListNode(0); ListNode handler = head; while(l1 != null && l2 != null) < if (l1.val else < handler.next = l2; l2 = l2.next; >handler = handler.next; > if (l1 != null) < handler.next = l1; >else if (l2 != null) < handler.next = l2; >return head.next; > >

Now let’s see the Recursive approach to solve the same problem in Java using Recursion.

/** * Definition for singly-linked list. * public class ListNode < * int val; * ListNode next; * ListNode() <>* ListNode(int val) < this.val = val; >* ListNode(int val, ListNode next) < this.val = val; this.next = next; >* > */ public class Solution < public ListNode mergeTwoLists(ListNode l1, ListNode l2) < if (l1 == null) return l2; if (l2 == null) return l1; ListNode handler; if(l1.val < l2.val) < handler = l1; handler.next = mergeTwoLists(l1.next, l2); >else < handler = l2; handler.next = mergeTwoLists(l1, l2.next); >return handler; > >

21. Merge Two Sorted Lists – Solution in C++

This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in C++ Programming Language.

/** * Definition for singly-linked list. * struct ListNode < * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) <>* ListNode(int x) : val(x), next(nullptr) <> * ListNode(int x, ListNode *next) : val(x), next(next) <> * >; */ class Solution < public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) < ListNode* temp = new ListNode(-1); ListNode* head = temp; while(l1!=NULL and l2!=NULL)< if(l1->valval)< head->next = l1; l1 = l1->next; > else < head->next = l2; l2 = l2->next; > head=head->next; > if(l1!=NULL) < head->next = l1; > else head->next = l2; return temp->next; > >;

Now let’s see the Recursive approach to solve the same problem in C++ using Recursion.

/** * Definition for singly-linked list. * struct ListNode < * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) <>* ListNode(int x) : val(x), next(nullptr) <> * ListNode(int x, ListNode *next) : val(x), next(next) <> * >; */ class Solution < public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) < if(l1 == NULL) < return l2; >if(l2 == NULL) < return l1; >if(l1 -> val val) < l1 ->next = mergeTwoLists(l1 -> next, l2); return l1; > else < l2 ->next = mergeTwoLists(l1, l2 -> next); return l2; > > >;

21. Merge Two Sorted Lists – Solution in Python

This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in Python Programming Language.

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next def mergeTwoLists1(self, l1, l2): dummy = cur = ListNode(0) while l1 and l2: if l1.val < l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 or l2 return dummy.next

Now let’s see the Recursive approach to solve the same problem in Python using Recursion.

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next def mergeTwoLists2(self, l1, l2): if not l1 or not l2: return l1 or l2 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2

Note: This problem 21. Merge Two Sorted Lists is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Источник

LeetCode #21 - Merge Two Sorted Lists

Hello fellow devs 👋! It’s time to solve a new LeetCode problem.

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

• The number of nodes in both lists is in the range [0, 50] .
• -100 ≤ Node.val ≤ 100
• Both l1 and l2 are sorted in non-decreasing order.

Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4]

Input: l1 = [], l2 = [0] Output: [0]

We will be given two sorted linked lists, and we need to merge them in such a way that the resultant list will also be sorted. Lists are sorted in the non-decreasing order, therefore, the resultant list should also be in non-decreasing order.

The approach is pretty straight forward. If you have worked with Merge Sort before, it is similar to that. We will use merge function of the merge sort to solve this problem. The steps are -

1. Check if any of the lists is empty.
2. First we need to determine the head of the resultant list. This head will be smaller of the heads of the given lists.
3. Loop through each node of the lists until one of the lists get traversed completely.
4. While traversing the lists, identify smaller of the nodes of the lists and add it to the resultant list.
5. Once the loop is complete, there may be a case where a list has nodes remaining. We will add those remaining nodes to the resultant list.

If the number of nodes are m and n in both lists, then the overall time complexity will be O(m + n) because we are traversing all the nodes of both the lists.

We are creating a list to store our result, but we are not using it as part of our intermediate computations, hence the space complexity according to me will be O(1).

public class MergeTwoSortedLists  private static ListNode mergeTwoLists(ListNode l1, ListNode l2)  // Check if ant of the lists are null if (l1 == null)  return l2; > if (l2 == null)  return l1; > // Head of the result list ListNode head; // Pointer for the resultant list ListNode temp; // Choose head which is smaller of the two lists if (l1.val  l2.val)  temp = head = new ListNode(l1.val); l1 = l1.next; > else  temp = head = new ListNode(l2.val); l2 = l2.next; > // Loop until any of the list becomes null while (l1 != null && l2 != null)  if (l1.val  l2.val)  temp.next = new ListNode(l1.val); l1 = l1.next; > else  temp.next = new ListNode(l2.val); l2 = l2.next; > temp = temp.next; > // Add all the nodes in l1, if remaining while (l1 != null)  temp.next = new ListNode(l1.val); l1 = l1.next; temp = temp.next; > // Add all the nodes in l2, if remaining while (l2 != null)  temp.next = new ListNode(l2.val); l2 = l2.next; temp = temp.next; > return head; > static class ListNode  int val; ListNode next; ListNode(int val)  this.val = val; > > >

class ListNode: def __init__(self, val=0, nextNode=None): self.val = val self.next = nextNode def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode: # Check if either of the lists is null if l1 is None: return l2 if l2 is None: return l1 # Choose head which is smaller of the two lists if l1.val  l2.val: temp = head = ListNode(l1.val) l1 = l1.next else: temp = head = ListNode(l2.val) l2 = l2.next # Loop until any of the list becomes null while l1 is not None and l2 is not None: if l1.val  l2.val: temp.next = ListNode(l1.val) l1 = l1.next else: temp.next = ListNode(l2.val) l2 = l2.next temp = temp.next # Add all the nodes in l1, if remaining while l1 is not None: temp.next = ListNode(l1.val) l1 = l1.next temp = temp.next # Add all the nodes in l2, if remaining while l2 is not None: temp.next = ListNode(l2.val) l2 = l2.next temp = temp.next return head

var mergeTwoLists = function (l1, l2)  // Check if either of the lists is null if (!l1)  return l2; > if (!l2)  return l1; > // Head of the new linked list - this is the head of the resultant list let head = null; // Reference of head which is null at this point let temp = head; // Choose head which is smaller of the two lists if (l1.val  l2.val)  temp = head = new ListNode(l1.val); l1 = l1.next; > else  temp = head = new ListNode(l2.val); l2 = l2.next; > // Loop until any of the list becomes null while (l1 && l2)  if (l1.val  l2.val)  temp.next = new ListNode(l1.val); l1 = l1.next; temp = temp.next; > else  temp.next = new ListNode(l2.val); l2 = l2.next; temp = temp.next; > > // Add all the nodes in l1, if remaining while (l1)  temp.next = new ListNode(l1.val); l1 = l1.next; temp = temp.next; > // Add all the nodes in l2, if remaining while (l2)  temp.next = new ListNode(l2.val); l2 = l2.next; temp = temp.next; > return head; >; function ListNode(val, next)  this.val = (val === undefined ? 0 : val) this.next = (next === undefined ? null : next) >

fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode?  var list1 = l1 var list2 = l2 // Check if ant of the lists are null if (list1 == null)  return list2 > if (list2 == null)  return list1 > // Head of the result list val head: ListNode // Pointer for the resultant list var temp: ListNode? // Choose head which is smaller of the two lists if (list1.`val`  list2.`val`)  head = ListNode(list1.`val`) temp = head list1 = list1.next > else  head = ListNode(list2.`val`) temp = head list2 = list2.next > // Loop until any of the list becomes null while (list1 != null && list2 != null)  if (list1.`val`  list2.`val`)  temp!!.next = ListNode(list1.`val`) list1 = list1.next > else  temp!!.next = ListNode(list2.`val`) list2 = list2.next > temp = temp.next > // Add all the nodes in l1, if remaining while (list1 != null)  temp!!.next = ListNode(list1.`val`) list1 = list1.next temp = temp.next > // Add all the nodes in l2, if remaining while (list2 != null)  temp!!.next = ListNode(list2.`val`) list2 = list2.next temp = temp.next > return head > class ListNode(var `val`: Int)  var next: ListNode? = null >

Congratulations 👏! We have solved the problem using merge function of merge sort.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.

Till next time… Happy coding 😄 and Namaste 🙏!

Источник

Merge Two Sorted Lists in Python: Know various methods

Sometimes we require to merge two lists that are sorted. This type of sorting is known as merge sorting. There are various ways to merge two sorted lists in python. In this entire tutorial, you will know how to merge two sorted lists in python with various examples.

Methods to Merge two sorted lists in Python

In this section, you will know all the methods you can use to merge two already sorted lists in python. Let’s know each of them.

Method 1: Using the sorted() function

You can use the python inbuilt function sorted() for sorting the two combined lists. Here you have to first append the list and then pass the combined list as an argument of the sorted() function. Execute the below lines of code and see the output.

Output

Method 2: Using the heapq merge

The second method to combine two already sorted lists is using the heapq module. It has a merge method that meger the lists in a sorted way. Just execute the below lines of code.

Method 3: Merge two sorted lists using stack

You can merge two sorted lists using a stack. In this method, you have to treat each sorted list as a stack. After that, continuously pop the smaller elements from the top of the stack and append the popped item to the list. It will continue to do so until the stack is empty. At last, the remaining elements of the list will be appended to the final list.

Execute the below lines of code and see the output.

These are the methods to merge two sorted lists. You can use any one of them. I hope you have liked this tutorial. If you have any queries then you can contact us for more help.

Join our list

Subscribe to our mailing list and get interesting stuff and updates to your email inbox.

We respect your privacy and take protecting it seriously

Thank you for signup. A Confirmation Email has been sent to your Email Address.

Источник