Simple solution with reverse traversing


  • 0
    Z

    public class Solution {

    public ListNode insertionSortList(ListNode head) {
        if(head == null) return head;
        ListNode pointer = new ListNode(-1);
        pointer.next = head;
        ListNode node = head.next;
        while(node != null){
            int key = node.val;
            ListNode cur = head;
            ListNode lastLower = pointer;
            // System.out.println(cur+" "+node);
            while(cur!= node){
                if(cur.val < key){
                    lastLower = cur;
                }
                cur = cur.next;
                if(cur == null){
                    System.out.println("wtf?");
                    break;
                }
            }
            cur = lastLower.next;
            int prev = lastLower.val;
            while(cur != node){
                int tmp = cur.val;
                cur.val = prev;
                prev= tmp;
                cur = cur.next;
            }
            node.val = prev;
            lastLower.next.val = key;
            node = node.next;
        }
        return head;
    }
    

    }


Log in to reply
 

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