How to merge ordered linked lists in Java

Question

Merge two ascending linked lists into a new ascending linked list and return. The new linked list is formed by concatenating all the nodes of the two given linked lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

8e99a69fbe029cd4e2b854e244eab143Input:128dba7a3a77be0113eb0bea6ea0a5d0l1 = [], l2 = []
8e99a69fbe029cd4e2b854e244eab143Output: 128dba7a3a77be0113eb0bea6ea0a5d0[]

Example 3:

Input: l1 = [] , l2 = [0]
Output: [0]

Idea

Version 1

• Create an empty linked list nList

• When both linked lists (l1, l2) are not empty, compare the values ​​of the first elements of the two linked lists, take the smallest one and add it to the new linked list Then the head pointer of the small linked list points to the next bit, and the pointer of nList also points to the next bit

• If both linked lists are not empty yet, continue to loop

• If one of the two linked lists is empty, then splice the non-empty linked list to the back of nList

• Finally return the next of nList as the head of the new linked list Node

Version 2

• First determine whether the two linked lists are empty, and return the empty linked list directly if they are empty. If it is not empty, continue going down

• Determine which of the head nodes of l1 and l2 is smaller, then save this node as the head node, and the subsequent nodes will be spliced ​​at this node at a time Above.

• The following ideas are the same as version one

Answer

Version one

Create a new node and replace the original The linked lists are transferred to the new linked list

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode   = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        all.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        all = all.next;
    }
    all.next = list1 != null ? list1 : list2;
    return head.next;
}

Version 2

Select one from the original linked list for integration, and does not apply to any new memory

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null || list2 == null) {
        return list1 == null ? list2 : list1;
    }
    ListNode head = list1.val <= list2.val ? list1 : list2;
    if (list1.val <= list2.val)
        list1 = list1.next;
    else
        list2 = list2.next;
    ListNode tmp = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        tmp.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        tmp = tmp.next;
    }
    tmp.next = list1 != null ? list1 : list2;
    return head;
}

The above is the detailed content of How to merge ordered linked lists in Java. For more information, please follow other related articles on the PHP Chinese website!