I think it would be the optimal solution, but don't know what's wrong with runtime error


  • 0
    S

    From seeing several most voted solutions, most of them are to store two queues and link them finally. However, I cam up with another solution, the idea was form the insertion sort.
    EX. 1->4->3->2->5->2 X= 3

    step 1: find the first node that bigger than the pivot (4 in this example)
    step 2: do a while loop from head, whenever finding a node that is smaller than pivot, we will insert it before the firstBig node

    below is my java code, but it always shows runtime error due to a nullPointerException. I cannot find the bug, is there anybody could help me?

    Please don't give me a downvote, I have tried to solve this problem for more than 2 hours and the main reason I posted it is to share my thinking. Thanks.

    public ListNode partition(ListNode head, int x) {
            //same way with insertion sort 
            if(head == null || head.next == null) return head;
            ListNode cur = head;
            ListNode next = head.next;//next means the next first smaller node after the cur
            ListNode prevNext = head;// prev node of the next node
            ListNode dummy = new ListNode(-1);
            ListNode prev = dummy;//prev means the last smaller node before the cur
            ListNode firstBig;
            
            //first find the first node that bigger or equal than pivot node
            while(cur != null && cur.val < x) { 
                cur = cur.next;
            }
            if(cur == null) return dummy.next;
            else { 
                 firstBig = cur;
                 cur = head;
            }
            
            while(cur != null) { 
                if(cur.val >= x) { 
                   //find the fisrt smaller node after the cur
                   while(next != null && next.val >= x ) { 
                       prevNext = next;
                       next = next.next;
                   }
                   if(next != null) { 
                       //next node found
                       prevNext.next = next.next;
                       prev.next = next;
                       next.next = firstBig;
                   } else { 
                       break;//all the following node are larger than pivot
                   }
                }
                prev = prev.next;
                cur = cur.next;
                next = cur.next;
            }
            return dummy.next;
        }

Log in to reply
 

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