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
CodePudding user response:
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 tohead
, andfollow.next = null
will just mutate the dummy node that was prepended before thehead
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 thewhile
condition so at least one iteration will be made. Also, you can do this without a third reference (follow
).In
merge
, thefirst
andsecond
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;
}