Just to recap, A linked list<\/a> is a linear data structure in which elements are stored in nodes. Each node points to the next node in the sequence. When we say the list is sorted, it means that the elements are arranged in ascending or descending order.<\/p>\n\n\n\n Merging two sorted linked lists preserves this order, which makes it easier for search algorithms to perform efficiently. We usually find the data in two different lists and it becomes necessary to join them to work on it. Sometimes, we need to present the output in a combined way.<\/p>\n\n\n\n Here is the problem statement: We are given 2 sorted linked lists, sorted in ascending order and we have to merge them in a way that maintains the sorted order.<\/strong><\/p>\n\n\n\n Let\u2019s look at an example,<\/p>\n\n\n\n LinkedList 1 = 1\u2192 3\u2192 6<\/p>\n\n\n\n LinkedList 2 = 2\u2192 4\u2192 5<\/p>\n\n\n\n Resultant List = 1\u2192 2\u2192 3\u2192 4\u2192 5\u2192 6<\/p>\n\n\n We can see the resultant list is sorted and contains the elements of both lists.<\/p>\n\n\n\n The simplest way to solve it is by using the brute-force approach. We can create a dummy node with a value of 0 to simplify this node and merge our present lists to this in sorted order. We will iterate both lists and keep adding the elements to this node.<\/p>\n\n\n\n Here are the steps involved in this straightforward technique:<\/p>\n\n\n\n The Time Complexity of this approach is O(max(m, n)), where m and n are the sizes of both the lists.\u00a0 The Space Complexity of this approach is O(max(m, n)).<\/p>\n\n\n\n In the recursive approach, we will use a recursion to merge two sorted linked lists.<\/strong> We first select the smaller of the current nodes from both lists and then recursively merge the remaining lists.<\/p>\n\n\n\n We will follow the same steps as we were following in the brute force approach. But we will use recursion<\/a> to do it easily. Following are the steps involved in merging two sorted linked lists using a recursive approach:<\/p>\n\n\n\n Here is the C++ program to merge two sorted lists using recursion:<\/p>\n\n\n\n Here is the Python program to merge two sorted linked lists:<\/p>\n\n\n\n You can implement it in Java as well:<\/p>\n\n\n\n Output:<\/strong><\/p>\n\n\n\n The time complexity of merging two sorted lists using recursion is O(n), where n is the total number of nodes in both linked lists. This is because the function processes each node exactly once, and the number of recursive calls is proportional to the total number of nodes in the input lists.<\/p>\n\n\n\n The Space Complexity is O(n) (due to the function call stack during recursion), O(1) auxiliary space.<\/p>\n\n\n\n In the end, here you can compare both approaches and see that recursive is the best one:<\/p>\n\n\n\n Another interesting problem related to linked lists is to detect a cycle<\/a>.<\/p>\n\n\n\n![\"Example](\"https:\/\/lh7-us.googleusercontent.com\/xd3S0qzZULZP3ZbBFyegJDI-6TEsZN0bL8ozd0rP_DFZISfbV3ztmSDxaffFb_ux4vRwgo4YRStuaJgyyPny4Wvkz1DEkwzA4SybF1Svv7HOMN_zNVPOSoI55hiNz-bPEP-MEhf4O2SDMeY9M3sLYqc\")
Brute Force Approach<\/strong><\/h2>\n\n\n\n
\n
![\"create](\"https:\/\/lh7-us.googleusercontent.com\/FgGH6Z0qh05AshI6Hs2ULK0fztymkS4cdMFFBLMW5T0nuDQbhfo__PV71QqBO-VHdAJXyvbzeASDSYSgiFTK68wVwMffuks32aYJUBfZUQl_oYokm1ZBDuMQKx585ql39ti4ZClaLVqDa7oEwau1nW0\")
\n
![\"create](\"https:\/\/lh7-us.googleusercontent.com\/IDL7cZSUjkk_AA5q649p-hfmd02vIfpaM6aT5z7VI6fYnWuo2hMynrwIj2gw-1SY3UUW45kSIncoUKaewltQY_iLF7VaTBKZtb8A1CwtgMZ4XWhZ5GWW7CmIKPE-6bCJZQBsx0ugKCgiWvbu2fn7Mzs\")
\n
![\"Compare](\"https:\/\/lh7-us.googleusercontent.com\/h4Ncoe3faOYHybUywU7GFWrYfkirL9TDxrBvV2A2bi0AWUtjQuZra3_9Ws_nFRUyalIbeqQCyby6MUk4jtgNIP632kMB_n_xoIwU03kIGqFWJRCAE_iCOsRY-ysc2gc806Gc0G649lxqRPnbqUaRxK0\")
\n
![\"append](\"https:\/\/lh7-us.googleusercontent.com\/Y4YAwVUa_toJJawU1X9myHpuV2-O5D6J3fCavrljR5WcuvhlOD1vHEWa_bXx_NV7UOk5h86we1HoDhBHiV65iR_pgjDXv7WvFipezpPK02e5syD7u7sW1tzzfb7quIwqf_CBW-Lep8rEaTYJ09ErH98\")
\n
![\"Return](\"https:\/\/lh7-us.googleusercontent.com\/0ZXgb9xDcDYhThGPpTtgD7_7orJgDngXO1lKA88KxFo1JXRynf-dujqQRtMsZvPVrB8tC7bujK28oqNW7r4D9j3taqrFYt6jXc3rG8LLsKxs_0-GxfyHo3-z29zEyW_5SCz9ay_caTys90O2iSJirFw\")
Recursive Approach to Merge Two-Sorted Lists<\/strong><\/h2>\n\n\n\n
\n
C++ Code<\/strong><\/h3>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\n\/\/ Definition for singly-linked list.\nstruct ListNode {\n int val;\n ListNode* next;\n ListNode(int x) : val(x), next(nullptr) {}\n};\n\nListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {\n \/\/ Base cases: if either list is empty, return the other list\n if (!l1) return l2;\n if (!l2) return l1;\n\n \/\/ Choose the smaller value as the current node\n if (l1->val < l2->val) {\n \/\/ Recursively merge the rest of the lists starting from l1->next and l2\n l1->next = mergeTwoLists(l1->next, l2);\n return l1;\n } else {\n \/\/ Recursively merge the rest of the lists starting from l1 and l2->next\n l2->next = mergeTwoLists(l1, l2->next);\n return l2;\n }\n}\n\nint main() {\n \/\/ Example usage\n \/\/ Create sorted linked lists\n ListNode* list1 = new ListNode(1);\n list1->next = new ListNode(3);\n list1->next->next = new ListNode(6);\n\n ListNode* list2 = new ListNode(2);\n list2->next = new ListNode(4);\n list2->next->next = new ListNode(5);\n\n \/\/ Merge the lists\n ListNode* mergedList = mergeTwoLists(list1, list2);\n\n \/\/ Print the merged list\n while (mergedList) {\n cout << mergedList->val << " ";\n mergedList = mergedList->next;\n }\n\n return 0;\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\n
class ListNode:\n def __init__(self, val=0, next=None):\n self.val = val\n self.next = next\n\ndef mergeTwoLists(l1, l2):\n # Create a dummy node to serve as the head of the merged list\n dummy = ListNode()\n current = dummy\n\n # Loop until one of the lists is empty\n while l1 and l2:\n if l1.val < l2.val:\n # Attach the current node to the smaller node from l1\n current.next = l1\n l1 = l1.next\n else:\n # Attach the current node to the smaller node from l2\n current.next = l2\n l2 = l2.next\n\n # Move the current pointer to the last node\n current = current.next\n\n # Attach the remaining nodes from the non-empty list (if any)\n if l1:\n current.next = l1\n elif l2:\n current.next = l2\n\n # Return the merged list starting from the dummy node's next\n return dummy.next\n\n# Example usage\nlist1 = ListNode(1, ListNode(3, ListNode(6)))\nlist2 = ListNode(2, ListNode(4, ListNode(5)))\n\nmergedList = mergeTwoLists(list1, list2)\n\n# Print the merged list\nwhile mergedList:\n print(mergedList.val, end=" ")\n mergedList = mergedList.next<\/pre><\/div>\n\n\n\n
Java Code<\/strong><\/h3>\n\n\n\n
public class MergeSortedLinkedLists {\n static class ListNode {\n int val;\n ListNode next;\n\n ListNode(int x) {\n val = x;\n next = null;\n }\n}\n\n public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {\n \/\/ Create a dummy node to simplify the code\n ListNode dummy = new ListNode(0);\n ListNode current = dummy;\n\n \/\/ Iterate while both lists are not empty\n while (l1 != null && l2 != null) {\n if (l1.val < l2.val) {\n current.next = l1;\n l1 = l1.next;\n } else {\n current.next = l2;\n l2 = l2.next;\n }\n current = current.next;\n }\n\n \/\/ If one list is not empty, append the remaining nodes\n if (l1 != null) {\n current.next = l1;\n } else {\n current.next = l2;\n }\n\n \/\/ Return the merged list starting from the next of the dummy node\n return dummy.next;\n }\n\n \/\/ Helper method to print the merged list\n public static void printList(ListNode head) {\n while (head != null) {\n System.out.print(head.val + " ");\n head = head.next;\n }\n System.out.println();\n }\n\n public static void main(String[] args) {\n \/\/ Example usage\n ListNode list1 = new ListNode(1);\n list1.next = new ListNode(3);\n list1.next.next = new ListNode(6);\n\n ListNode list2 = new ListNode(2);\n list2.next = new ListNode(4);\n list2.next.next = new ListNode(5);\n\n \/\/ Merge the lists\n ListNode mergedList = mergeTwoLists(list1, list2);\n\n \/\/ Print the merged list\n System.out.println("Merged List:");\n printList(mergedList);\n }\n}<\/pre><\/div>\n\n\n\n1 2 3 4 5 6 <\/code><\/pre>\n\n\n\nApproach<\/strong><\/td> Time complexity<\/strong><\/td> Space complexity<\/strong><\/td> Details<\/strong><\/td><\/tr> Brute force <\/td> O(max(m, n))<\/td> O(max(m, n))<\/td> Create a dummy node with a value of 0 to simplify this node and merge our present lists to this in sorted order.<\/td><\/tr> Recursive <\/td> O(n)<\/td> O(1)<\/td> Using recursion to save time and space.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n Conclusion <\/strong><\/h2>\n\n\n\n