Try to implement quickSort, but it is stackoverflow for large size, any suggestions?


  • 0
    W
        /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode sortList(ListNode head) {
            if(head==null) return head;
            if(head.next == null) return head;
            ListNode left = head;
            ListNode right = head;
            while(right.next!=null) right = right.next;// To get final node
            head = quickSort(head,right);
            return head;
        }
        public ListNode quickSort(ListNode left,ListNode right){
            if(left==null||left==right) return left;
            ListNode l = left;
            ListNode r = left.next;
            ListNode prer = left;
            ListNode v = l;
            while(l!=null&&r!=null&&r!=right.next){
                while(r!=null&&r!=right.next&&r.val>v.val){
                    prer = r;
                    r = r.next;
                }
                if(r!=null&&r!=right.next){//r is small than l
                    ListNode temp = r.next;
                    r.next = l;
                    l = r;
                    r = temp;
                    prer.next = temp;
                }
            }
            ListNode m = l;
            while(m!=null&&m.next!=v){//To find a node which is pre of v
                m = m.next;
            }
            if(l!=null&&m!=null&&m.val<v.val){
                left = quickSort(l,m);
            }
            if(v.next!=null&&v.next.next!=null) v.next = quickSort(v.next,right);
            return left;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.