merge sort linkedlist - stackoverflow error

Question

I am trying to solve leetcode-148 (https://leetcode.com/problems/sort-list/) i.e. sort given LinkedList, but am getting a stackoverflow error. so far I have tried dry running but am not seeing where the issue could occur.. the base condition of the recursion seems to be right but looks like I am missing something if someone sees what I am not seeing..

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head==null || head.next==null) return head;

        ListNode follow = new ListNode(0);
        follow.next=head;
        ListNode fast = head;
        ListNode slow = head;
        
        // Find the mid-point of the list
        while (fast.next!=null && fast.next.next!=null) {
            slow=slow.next;
            fast=fast.next.next;
            follow=follow.next;
        }

        // Split the list
        follow.next = null;
        
        // Sort each half
        ListNode first = sortList(head);
        ListNode second = sortList(slow);
        
        // Merge
        return merge(first, second);
    }
    
    private ListNode merge(ListNode first, ListNode second) {
        if (first==null) return second;
        if (second==null) return first;
        
        ListNode result = new ListNode(0);
        ListNode head = result;
        
        while (first!=null && second!=null) {
            if (first.val<second.val) {
                result.next = first;
            } else {
                result.next = second;
            }
            
            result=result.next;
        }
        
        if (first!=null) {
            result.next = first;
            result=result.next;
        }
        
        if (second!=null) {
            result.next = second;
            result=result.next;
        }
        
        return head.next;
    }
}

Here's the error

WARNING: A command line option has enabled the Security Manager
WARNING: The Security Manager is deprecated and will be removed in a future release
java.lang.StackOverflowError
  at line 31, Solution.sortList
  at line 31, Solution.sortList
  at line 31, Solution.sortList
  at line 31, Solution.sortList
  at line 31, Solution.sortList

Evade

"sort 2 given LinkedLists": the code challenge is about sorting 1 linked list. – Eldaelden

Technically, a top down merge sort for linked list fails the stated goal of O(1) space, since O(log(n)) space is used for the stack. A bottom up merge sort for linked lists meets the goals, and is also faster for a large list with scattered nodes. – Scintillometer

Answer 1

There are two issues:

• When sortList is called with a list that has 2 nodes, then after the first loop (which makes no iterations), slow will be equal to head, and follow.next = null will just mutate the dummy node that was prepended before the head node. So essentially the linked list wasn't split, and the recursive call is on the same list, leading to infinite recursion. Solve this by changing the while condition so at least one iteration will be made. Also, you can do this without a third reference (follow).

• In merge, the first and second references do not move forward, so the loop will be infinite.

Here is corrected code:

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode fast = head.next;
    ListNode slow = head;
    
    // Find the mid-point of the list
    while (fast != null && fast.next != null) { // iterate at least once
        slow = slow.next;
        fast = fast.next.next;
    }

    // Split the list
    ListNode second = slow.next;
    slow.next = null;
    
    // Sort each half
    head = sortList(head);
    second = sortList(second);
    
    // Merge
    return merge(head, second);
}

private ListNode merge(ListNode first, ListNode second) {
    ListNode result = new ListNode(0);
    ListNode head = result;
    
    while (first != null && second != null) {
        if (first.val < second.val) {
            result.next = first;
            first = first.next; // move forward
        } else {
            result.next = second;
            second = second.next;
        }            
        result = result.next;
    }
    if (first != null) {
        result.next = first;
        result = result.next;
    }
    if (second != null) {
        result.next = second;
        result = result.next;
    }
    return head.next;
}

Eldaelden

Excellent!! Thank you!! That makes it crystal clear! Ya I missed the merge pointer increment part, my bad (pretty sure I had that coded but somehow ended up messing it up). The root cause makes perfect sense. You are amazing! :) – Evade