java 为什么在链表的前半部分调用mergesort时显示堆栈溢出异常

fgw7neuy 于 2023-01-29 发布在 Java

关注(0)|答案(2)|浏览(111)

public class Solution {

    public static LinkedListNode<Integer> mergeSort(LinkedListNode<Integer> head) {
        //Your code goes 
         LinkedListNode slow=head, fast=head, temp=head;
         while(fast!=null && fast.next!=null){
             temp=slow;
             fast=fast.next.next;
             slow=slow.next;
         }
          temp.next=null;
          LinkedListNode left_side=mergeSort(head);
          LinkedListNode right_side=mergeSort(slow);

          return merge(left_side, right_side);
    }

    public static LinkedListNode merge(LinkedListNode<Integer> head1, LinkedListNode<Integer> head2){
       LinkedListNode temp_node=new LinkedListNode(0);
       LinkedListNode current_node= temp_node;

       while(head1!=null && head2!=null){
           if(head1.data<=head2.data){
               current_node.next=head1;
               head1=head1.next;
           }else{
               current_node.next=head2;
               head2=head2.next;
           }
           current_node=current_node.next;
       }
       if(head1!=null){
          current_node.next=head1;
          head1=head1.next;
       }
       if(head2!=null){
           current_node=head2;
           head2=head2.next;
       }
       
       return temp_node.next;

   }
}

我期待一个排序列表，但我得到了一个StackOverflowError。
我该怎么改正呢？错误是专门针对我在链表左侧调用mergSort的那一行显示的，我该怎么办呢？

Java

来源：https://stackoverflow.com/questions/75219008/why-is-it-showing-stack-overflow-exception-when-i-call-mergesort-on-the-first-ha

2条答案

按热度按时间

cbjzeqam1#

您正在mergeSort（）方法中使用递归，并且mergeSort函数没有退出条件。在调用递归之前，您应该有一个退出条件。否则，它将继续调用相同的方法，直到堆栈满为止。因此，堆栈溢出错误。

赞(0）回复(0）举报 2023-01-29

j91ykkif2#

thumbs已经回答了这个问题。如果你感兴趣，这里有自底向上和自顶向下合并排序单链表的例子。自底向上比较快，快多少取决于节点的数量和节点是否分散（缓存未命中）。将列表复制到一个数组中，排序数组，然后从数组创建一个新的排序列表更快。两个例子的合并函数是相同的：执行if（true）{head ...}... while（true）{dest ...}以避免使用虚节点（这避免了在每次调用合并时分配和释放虚节点）。
自下而上

// bottom up merge sort for single link list
    static Node sortbu(Node head) {
        final int NUMLIST = 32;
        Node[] alist = new Node[NUMLIST];
        Node node;
        Node next;
        int i;
        // if < 2 nodes, return
        if(head == null || head.next == null)
            return null;
        node = head;
        // merge node into array
        while(node != null){
            next = node.next;
            node.next = null;
            for(i = 0; (i < NUMLIST) && (alist[i] != null); i++){
                node = merge(alist[i], node);
                alist[i] = null;
            }
            if(i == NUMLIST)   // don't go past end of array
                i--;
            alist[i] = node;
            node = next;
        }
        // node == null
        // merge array into single list
        for(i = 0; i < NUMLIST; i++)
            node = merge(alist[i], node);
        return node;
    }

    // merge two already sorted lists
    static Node merge(Node list0, Node list1) {
        if(list0 == null)
            return list1;
        if(list1 == null)
            return list0;
        Node head;
        Node dest;
        if(true){
            if(list0.data <= list1.data){
                head = list0;
                dest = list0;
                list0 = list0.next;
                if(list0 == null){
                    dest.next = list1;
                    return head;
                }
            } else {
                head = list1;
                dest = list1;
                list1 = list1.next;
                if(list1 == null){
                    dest.next = list0;
                    return head;
                }
            }
        }
        while(true){
            if(list0.data <= list1.data){
                dest.next = list0;
                dest = list0;
                list0 = list0.next;
                if(list0 == null){
                    dest.next = list1;
                    return head;
                }
            } else {
                dest.next = list1;
                dest = list1;
                list1 = list1.next;
                if(list1 == null){
                    dest.next = list0;
                    return head;
                }
            }
        }
    }

自上而下

// top down merge sort for single link list entry function
    static Node sorttd(Node head) {
        int n = size(head);
        if(n < 2)
            return head;
        head = sorttdr(head, n);
        return head;
    }

    // top down merge sort for single link list recursive function
    static Node sorttdr(Node head, int n) {
        if(n < 2)
            return head;
        int n2 = (n/2);
        Node node = advance(head, n2-1);
        Node next = node.next;
        node.next = null;
        head = sorttdr(head, n2);
        next = sorttdr(next, n-n2);
        head = merge(head, next);
        return head;
    }

    // return size of list
    static int size(Node head) {
    int i = 0;
        while(head != null){
            head = head.next;
            i++;
        }
        return i;
    }

    // advance to node n
    static Node advance(Node head, int n) {
        while(0 < n--)
            head = head.next;
        return head;
    }

    // merge two already sorted lists
    static Node merge(Node list0, Node list1) {
        if(list0 == null)
            return list1;
        if(list1 == null)
            return list0;
        Node head;
        Node dest;
        if(true){
            if(list0.data <= list1.data){
                head = list0;
                dest = list0;
                list0 = list0.next;
                if(list0 == null){
                    dest.next = list1;
                    return head;
                }
            } else {
                head = list1;
                dest = list1;
                list1 = list1.next;
                if(list1 == null){
                    dest.next = list0;
                    return head;
                }
            }
        }
        while(true){
            if(list0.data <= list1.data){
                dest.next = list0;
                dest = list0;
                list0 = list0.next;
                if(list0 == null){
                    dest.next = list1;
                    return head;
                }
            } else {
                dest.next = list1;
                dest = list1;
                list1 = list1.next;
                if(list1 == null){
                    dest.next = list0;
                    return head;
                }
            }
        }
    }

赞(0）回复(0）举报 2023-01-29

我来回答

java 为什么在链表的前半部分调用mergesort时显示堆栈溢出异常

2条答案

相关问题

热门标签

最新问答