{"id":663,"date":"2025-07-15T13:45:35","date_gmt":"2025-07-15T08:15:35","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=663"},"modified":"2025-07-15T13:45:37","modified_gmt":"2025-07-15T08:15:37","slug":"sort-list-leetcode-148","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/","title":{"rendered":"Sort List | Leetcode 148 | Optimal Merge Sort"},"content":{"rendered":"\n<p>Given the&nbsp;<code>head<\/code>&nbsp;of a linked list, return&nbsp;<em>the list after sorting it in&nbsp;<strong>ascending order<\/strong><\/em>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/sort-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/09\/14\/sort_list_1.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> head = [4,2,1,3]<br><strong>Output:<\/strong> [1,2,3,4]<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/09\/14\/sort_list_2.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> head = [-1,5,3,4,0]<br><strong>Output:<\/strong> [-1,0,3,4,5]<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> head = []<br><strong>Output:<\/strong> []<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The number of nodes in the list is in the range\u00a0<code>[0, 5 * 10<sup>4<\/sup>]<\/code>.<\/li>\n\n\n\n<li><code>-10<sup>5<\/sup> &lt;= Node.val &lt;= 10<sup>5<\/sup><\/code><\/li>\n<\/ul>\n\n\n\n<p><strong>Follow up:<\/strong>&nbsp;Can you sort the linked list in&nbsp;<code>O(n logn)<\/code>&nbsp;time and&nbsp;<code>O(1)<\/code>&nbsp;memory (i.e. constant space)?<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-fb2abc74-01b0-4022-b7c3-29c463fa50f8\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#0-solution-1-brute-force-approach-using-array\" style=\"\">Solution 1: Brute Force Approach (Using Array)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#8-solution-2-optimal-approach-merge-sort\" style=\"\">Solution 2: Optimal Approach (Merge Sort)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/sort-list-leetcode-148\/#16-summary\" style=\"\">Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-brute-force-approach-using-array\">Solution 1: Brute Force Approach (Using Array)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like organizing a messy bookshelf! One simple way is to take all the books down, put them in a pile, sort that pile, and then put the books back on the shelf in the correct order. We do the same thing here &#8211; extract all values from the linked list, sort them in an array, and then put them back in the same linked list structure.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Extract Values<\/strong>: Walk through the linked list and collect all node values in an array<\/li>\n\n\n\n<li><strong>Sort Array<\/strong>: Use the built-in sort function to sort the array of values<\/li>\n\n\n\n<li><strong>Put Back Values<\/strong>: Walk through the linked list again and replace each node&#8217;s value with the sorted values<\/li>\n\n\n\n<li><strong>Return Result<\/strong>: The linked list now contains values in sorted order<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def sortList(self, head: Optional[ListNode]) -&gt; Optional[ListNode]:\n        values = []\n        current_node = head\n\n        # First pass: Collect all values from the linked list\n        while current_node:\n            values.append(current_node.val)  # Add current node's value to array\n            current_node = current_node.next\n\n        # Sort the values using built-in sort\n        values.sort()\n\n        # Second pass: Reassign the sorted values to the linked list nodes\n        current_node = head\n        index = 0\n        while current_node:\n            current_node.val = values[index]  # Replace with sorted value\n            index += 1\n            current_node = current_node.next\n\n        return head\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">sortList<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">head<\/span><span style=\"color: #D4D4D4\">: Optional[ListNode]) -&gt; Optional[ListNode]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        values = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        current_node = head<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># First pass: Collect all values from the linked list<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> current_node:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            values.append(current_node.val)  <\/span><span style=\"color: #6A9955\"># Add current node&#39;s value to array<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            current_node = current_node.next<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Sort the values using built-in sort<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        values.sort()<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Second pass: Reassign the sorted values to the linked list nodes<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        current_node = head<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        index = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> current_node:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            current_node.val = values[index]  <\/span><span style=\"color: #6A9955\"># Replace with sorted value<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            index += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            current_node = current_node.next<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> head<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>We use a two-pass approach here. In the first pass, we walk through the entire linked list and copy all the values into a regular array. Then we sort this array using Python&#8217;s built-in sort function, which is very efficient. In the second pass, we walk through the linked list again and replace each node&#8217;s value with the corresponding sorted value from our array. The structure of the linked list remains the same &#8211; only the values change.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>4 -&gt; 2 -&gt; 1 -&gt; 3<\/code><\/p>\n\n\n\n<p><strong>First Pass (Extract Values):<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Visit node 4: values =<\/li>\n\n\n\n<li>Visit node 2: values =<\/li>\n\n\n\n<li>Visit node 1: values =\u00a0<a href=\"https:\/\/leetcode.com\/problems\/sort-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n\n\n\n<li>Visit node 3: values =\u00a0<a href=\"https:\/\/leetcode.com\/problems\/sort-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n<\/ul>\n\n\n\n<p><strong>Sort Array:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>values.sort() \u2192 values =\u00a0<a href=\"https:\/\/leetcode.com\/problems\/sort-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n<\/ul>\n\n\n\n<p><strong>Second Pass (Put Back Values):<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Node 4 becomes 1:\u00a0<code>1 -> 2 -> 1 -> 3<\/code><\/li>\n\n\n\n<li>Node 2 becomes 2:\u00a0<code>1 -> 2 -> 1 -> 3<\/code><\/li>\n\n\n\n<li>Node 1 becomes 3:\u00a0<code>1 -> 2 -> 3 -> 3<\/code><\/li>\n\n\n\n<li>Node 3 becomes 4:\u00a0<code>1 -> 2 -> 3 -> 4<\/code><\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;<code>1 -&gt; 2 -&gt; 3 -&gt; 4<\/code><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\u00a0O(n log n) &#8211; The sorting step dominates the time complexity<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(n) &#8211; We store all values in the array<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like taking notes from a messy notebook, organizing those notes separately, and then rewriting them back in the same notebook in order. It&#8217;s easy to understand and implement, but requires extra space to store all the values temporarily.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-solution-2-optimal-approach-merge-sort\">Solution 2: Optimal Approach (Merge Sort)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>Imagine you have a huge pile of playing cards to sort. Instead of sorting the entire pile at once, you could split it into smaller piles, sort each small pile, and then merge the sorted piles back together. This is exactly what merge sort does! It&#8217;s like having a team of people where each person sorts a small pile, then they work together to combine all the sorted piles into one final sorted pile.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Base Case<\/strong>: If the list has 0 or 1 nodes, it&#8217;s already sorted<\/li>\n\n\n\n<li><strong>Split<\/strong>: Find the middle of the list and split it into two halves<\/li>\n\n\n\n<li><strong>Conquer<\/strong>: Recursively sort both halves<\/li>\n\n\n\n<li><strong>Merge<\/strong>: Combine the two sorted halves into one sorted list<\/li>\n\n\n\n<li><strong>Return<\/strong>: The merged result is our final sorted list<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def getMiddle(self, head: ListNode) -&gt; ListNode:\n        slow = head\n        fast = head\n        # Use slow and fast pointers to find middle\n        while fast.next and fast.next.next:\n            slow = slow.next      # Move slow 1 step\n            fast = fast.next.next # Move fast 2 steps\n        return slow  # Slow pointer ends at the middle (or just before)\n\n    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -&gt; ListNode:\n        dummy = ListNode()  # Dummy node to simplify merging\n        tail = dummy\n        \n        # Merge nodes by comparing values\n        while l1 and l2:\n            if l1.val &lt; l2.val:\n                tail.next = l1    # Take smaller value from l1\n                l1 = l1.next\n            else:\n                tail.next = l2    # Take smaller value from l2\n                l2 = l2.next\n            tail = tail.next\n\n        # Append remaining elements from either list\n        tail.next = l1 or l2\n        return dummy.next  # Skip the initial dummy node\n\n    def sortList(self, head: Optional[ListNode]) -&gt; Optional[ListNode]:\n        if not head or not head.next:  # Base case: empty or single-node list\n            return head\n\n        # Step 1: Split the list into two halves\n        mid = self.getMiddle(head)\n        left = head\n        right = mid.next\n        mid.next = None  # Disconnect the two halves\n\n        # Step 2: Recursively sort the two halves\n        left = self.sortList(left)\n        right = self.sortList(right)\n\n        # Step 3: Merge the sorted halves\n        return self.mergeTwoLists(left, right)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">getMiddle<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">head<\/span><span style=\"color: #D4D4D4\">: ListNode) -&gt; ListNode:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        slow = head<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        fast = head<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Use slow and fast pointers to find middle<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> fast.next <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> fast.next.next:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            slow = slow.next      <\/span><span style=\"color: #6A9955\"># Move slow 1 step<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            fast = fast.next.next <\/span><span style=\"color: #6A9955\"># Move fast 2 steps<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> slow  <\/span><span style=\"color: #6A9955\"># Slow pointer ends at the middle (or just before)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">mergeTwoLists<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">l1<\/span><span style=\"color: #D4D4D4\">: ListNode, <\/span><span style=\"color: #9CDCFE\">l2<\/span><span style=\"color: #D4D4D4\">: ListNode) -&gt; ListNode:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dummy = ListNode()  <\/span><span style=\"color: #6A9955\"># Dummy node to simplify merging<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        tail = dummy<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Merge nodes by comparing values<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> l1 <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> l2:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> l1.val &lt; l2.val:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                tail.next = l1    <\/span><span style=\"color: #6A9955\"># Take smaller value from l1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                l1 = l1.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                tail.next = l2    <\/span><span style=\"color: #6A9955\"># Take smaller value from l2<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                l2 = l2.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            tail = tail.next<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Append remaining elements from either list<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        tail.next = l1 <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> l2<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dummy.next  <\/span><span style=\"color: #6A9955\"># Skip the initial dummy node<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">sortList<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">head<\/span><span style=\"color: #D4D4D4\">: Optional[ListNode]) -&gt; Optional[ListNode]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> head <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> head.next:  <\/span><span style=\"color: #6A9955\"># Base case: empty or single-node list<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> head<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Step 1: Split the list into two halves<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        mid = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.getMiddle(head)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        left = head<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        right = mid.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        mid.next = <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Disconnect the two halves<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Step 2: Recursively sort the two halves<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        left = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.sortList(left)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        right = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.sortList(right)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Step 3: Merge the sorted halves<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.mergeTwoLists(left, right)<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This solution uses the divide-and-conquer approach with three helper functions. The&nbsp;<code>getMiddle<\/code>&nbsp;function uses the tortoise and hare technique to find the middle node. The&nbsp;<code>mergeTwoLists<\/code>&nbsp;function takes two sorted linked lists and merges them into one sorted list by comparing values. The main&nbsp;<code>sortList<\/code>&nbsp;function recursively splits the list in half, sorts each half, and then merges them back together. This process continues until we have single-node lists (which are already sorted), then builds up the final sorted list.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>4 -&gt; 2 -&gt; 1 -&gt; 3<\/code><\/p>\n\n\n\n<p><strong>Initial Call: sortList([4 -&gt; 2 -&gt; 1 -&gt; 3])<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Find middle: between 2 and 1<\/li>\n\n\n\n<li>Split: left = [4 -> 2], right = [1 -> 3]<\/li>\n\n\n\n<li>Recursively sort both halves<\/li>\n<\/ul>\n\n\n\n<p><strong>Left Half: sortList([4 -&gt; 2])<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Find middle: between 4 and 2<\/li>\n\n\n\n<li>Split: left = , right =<\/li>\n\n\n\n<li>Base case: both are single nodes, return as is<\/li>\n\n\n\n<li>Merge and \u2192 [2 -> 4]<\/li>\n<\/ul>\n\n\n\n<p><strong>Right Half: sortList([1 -&gt; 3])<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Find middle: between 1 and 3<\/li>\n\n\n\n<li>Split: left =\u00a0<a href=\"https:\/\/leetcode.com\/problems\/sort-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>, right =<\/li>\n\n\n\n<li>Base case: both are single nodes, return as is<\/li>\n\n\n\n<li>Merge\u00a0<a href=\"https:\/\/leetcode.com\/problems\/sort-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>\u00a0and \u2192 [1 -> 3]<\/li>\n<\/ul>\n\n\n\n<p><strong>Final Merge: mergeTwoLists([2 -&gt; 4], [1 -&gt; 3])<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Compare 2 and 1: take 1 \u2192\u00a0<a href=\"https:\/\/leetcode.com\/problems\/sort-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n\n\n\n<li>Compare 2 and 3: take 2 \u2192 [1 -> 2]<\/li>\n\n\n\n<li>Compare 4 and 3: take 3 \u2192 [1 -> 2 -> 3]<\/li>\n\n\n\n<li>Append remaining 4 \u2192 [1 -> 2 -> 3 -> 4]<\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;<code>1 -&gt; 2 -&gt; 3 -&gt; 4<\/code><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\u00a0O(n log n) &#8211; We divide the list log n times, and each merge takes O(n) time<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(log n) &#8211; Due to the recursion call stack (depth of recursion is log n)<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like organizing a large group of people by repeatedly splitting them into smaller groups, having each small group organize themselves, and then merging the organized groups back together. It&#8217;s more complex to understand but very efficient and doesn&#8217;t require extra space for storing all values like the brute force approach.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"16-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Difficulty<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Brute Force (Array)<\/td><td>O(n log n)<\/td><td>O(n)<\/td><td>Easy<\/td><td>Learning the concept<\/td><\/tr><tr><td>Optimal (Merge Sort)<\/td><td>O(n log n)<\/td><td>O(log n)<\/td><td>Hard<\/td><td>Production code<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The&nbsp;<strong>merge sort approach<\/strong>&nbsp;is generally preferred because it uses less space while maintaining the same time complexity. However, the brute force approach is more intuitive and easier to understand when you&#8217;re first learning about sorting algorithms.<\/p>\n\n\n\n<p>Both solutions achieve the same time complexity, but the merge sort solution is more elegant and space-efficient. It also demonstrates important concepts like divide-and-conquer, recursion, and the two-pointer technique. The key insight is that we can sort a linked list without converting it to an array by cleverly splitting, sorting, and merging the sublists!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given the&nbsp;head&nbsp;of a linked list, return&nbsp;the list after sorting it in&nbsp;ascending order. Here&#8217;s the [Problem Link] to begin with. Example 1: Input: head = [4,2,1,3]Output: [1,2,3,4] Example 2: Input: head = [-1,5,3,4,0]Output: [-1,0,3,4,5] Example 3: Input: head = []Output: [] Constraints: Follow up:&nbsp;Can you sort the linked list in&nbsp;O(n logn)&nbsp;time and&nbsp;O(1)&nbsp;memory (i.e. constant space)? Solution<\/p>\n","protected":false},"author":1,"featured_media":664,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,5],"tags":[18,29],"class_list":{"0":"post-663","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-hard","10":"tag-singly-linked-list"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/sort-linked-list-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/663","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=663"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/663\/revisions"}],"predecessor-version":[{"id":665,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/663\/revisions\/665"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/664"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=663"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=663"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=663"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}