Java 34ms solution, clear logic with separate insert method


  • 3
    Y

    using insertion sort logic. Insert each new node into a sorted linked list with dummy head.

      public class Solution {
            public ListNode insertionSortList(ListNode head) {
                ListNode sortedHeadDummy = new ListNode(0);
                ListNode curr = head;
                while (curr != null) {
                    ListNode next = curr.next;
                    insert(sortedHeadDummy, curr);
                    curr = next;
                }
                return sortedHeadDummy.next;
            }
            
            private void insert(ListNode dummyHead, ListNode target) {
                // left to right scan to insert the target node
                ListNode curr = dummyHead;
                while (curr.next != null && curr.next.val < target.val) {
                    curr = curr.next;
                }
                target.next = curr.next;
                curr.next = target;
            }
        }

  • 0
    D

    if you have a list:
    4 -> 2->3->1->null. it seems that since 4 is the first element that you are passing to insert() it's next will be set to itself, resulting in a loop at the end of the linked list instead of a null.
    by this lines:
    target.next = curr.next;
    curr.next = target;

    am I wrong?


Log in to reply
 

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