Java solution with N2 time complexity, why is it accepted, how to improve?


  • 0
    J
        public class Solution {
        public ListNode insertionSortList(ListNode head) {
            if (head == null) return null;
            ListNode newHead = head;
            ListNode pn, pnh, cur, prev;
            pn = head.next;
            pnh = head;
            pnh.next = null;
            while(pn != null) {
                cur = pn;
                pn = pn.next;
                pnh = newHead;
                prev = newHead;
                while (pnh != null) {
                    if (cur.val <= pnh.val) {
                        cur.next = pnh;
                        if (prev.val < cur.val) {
                            prev.next = cur;
                        } else {
                            newHead = cur;
                        }
                        break;
                    } else {
                        prev = pnh;
                        pnh = pnh.next;
                        if (pnh == null) {
                            prev.next = cur;
                            cur.next = null;
                        }
                    }
                }
            } 
            return newHead;        
        }
    }

Log in to reply
 

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