问答

当前位置
  • 首页
  • 问答
  • 104. Merge K Sorted Lists - 分治解法栈溢出stack overflow错误

104. Merge K Sorted Lists - 分治解法栈溢出stack overflow错误

  • Ta: 李玉哲

以下是我自己写的分治解法,我看着跟九章的实现没什么两样,为什么领扣会RE说stack overflow了呢?

https://www.jiuzhang.com/solution/merge-k-sorted-lists/

Runtime Error
Input
[2->4->null,null,-1->null]
Expected
-1->2->4->null
Console Logs
Exception in thread "main" java.lang.StackOverflowError at java.util.ArrayList$SubList.subList(ArrayList.java:1217) at Solution.mergeKLists(Solution.java:28) at Solution.mergeKLists(Solution.java:29) at Solution.mergeKLists(Solution.java:29) at Solution.mergeKLists(Solution.java:29) at Solution.mergeKLists(Solution.java:29) at Solution.mergeKLists(Solution.java:29) at
...

```
public ListNode mergeKLists(List lists) {
if (lists == null || lists.isEmpty()) {
return null;
}
if (lists.size() == 1) {
return lists.get(0);
}

    int start = 0, end = lists.size() - 1;
    // if (start < end) {
        int mid = (end - start) / 2 + start;
        ListNode left = mergeKLists(lists.subList(start, mid));
        ListNode right = mergeKLists(lists.subList(mid, end + 1));
    //}

    return mergeTwoLists(left, right);
}

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            cur.next = l1; //here, dummy.next is updated to be l1 which is head to be returned
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next; //head won't be changed because cur is not pointing to head anymore since this line
    }
    if (l1 == null) {
        cur.next = l2;
    }
    if (l2 == null) {
        cur.next = l1;
    }
    return dummy.next;
}

1 个回复

2019-09-13 Steven He

mergeKLists中的问题。改成ListNode left = mergeKLists(lists.subList(start, mid + 1))和ListNode right = mergeKLists(lists.subList(mid + 1, end + 1))就可以了,完整代码如下:

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {  
        if (lists == null || lists.isEmpty()) {
            return null;
        }
        System.out.println("lists.size(): " + lists.size());
        if (lists.size() == 1) {
            return lists.get(0);
        }

        int start = 0, end = lists.size() - 1;
        // if (start < end) {
        int mid = (end - start) / 2 + start;
        System.out.println("start and mid: " + start + "\t"+ (mid));
        ListNode left = mergeKLists(lists.subList(start, mid + 1));
        System.out.println("mid and end: " + (mid + 1) + "\t"+ end);
        ListNode right = mergeKLists(lists.subList(mid + 1, end + 1));
        //}

        return mergeTwoLists(left, right);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1; //here, dummy.next is updated to be l1 which is head to be returned
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next; //head won't be changed because cur is not pointing to head anymore since this line
        }
        if (l1 == null) {
            cur.next = l2;
        }
        if (l2 == null) {
            cur.next = l1;
        }
        return dummy.next;
    }
}

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1