Java ac solution without recursion


  • 0
    Y
    /**
     * Just like the merge process of MergeSort.
     * Compare the current node of 2 lists and put the smaller one into the result list and move the pointer of the list whose node has just be taken to its next one. 
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode curr = head;
        while (l1 != null && l2 != null) {
            if (l1.val >= l2.val) {
                curr.next = l2;
                l2 = l2.next;
            } 
            else {
                curr.next = l1;
                l1 = l1.next;
            }
            curr = curr.next;
        }
        if (l1 != null) curr.next = l1;
        else if (l2 != null) curr.next = l2;
        return head.next;
    }
    

  • 1

    why use head.next in the last line?


  • 0
    Y

    I think it is because head starts from 0, head.next points to curr


  • 0
    Y

    @Harrywithcode Because head is only a useless node in order to solve the initial condition where there is no node at all in the new list. Since we want to add the first node into the new list, we need it to be after some node, and head is this node. Thus head.next is the actual beginning of the merged new list.


  • 1

    @YaokaiYang 哦了,我明白了,谢谢,基础知识掌握的不劳,一回忆就想起来了


Log in to reply
 

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