Merge Two Sorted Linked Lists

1. Problem Description

Given two monotonically increasing linked lists, merge them into one linked list that remains monotonically non-decreasing.

2. Approach

• Iteration: similar to the merge step of merge sort
• Recursion

3. Implementation

3.1. Iteration

• java

public class 合并两个排序的链表
{
    public ListNode Merge(ListNode list1, ListNode list2)
    {
        // Check parameters
        if (list1 == null)
        {
            return list2;
        }
        if (list2 == null)
        {
            return list1;
        }

        // Determine the head node
        ListNode newHead = list1.val < list2.val ? list1 : list2;
        ListNode current = newHead;
        // Traverse both linked lists at the same time
        while (list1 != null && list2 != null)
        {
            // Link the smaller node into the merged list
            ListNode nextNode = null;
            if (list1.val < list2.val)
            {
                nextNode = list1;
                list1 = list1.next;
            }
            else
            {
                nextNode = list2;
                list2 = list2.next;
            }
            current.next = nextNode;
            current = current.next;
        }

        // Append the remaining list
        if (list1 != null)
        {
            current.next = list1;
        }
        else if (list2 != null)
        {
            current.next = list2;
        }

        return newHead;
    }
}

• go

// Iterative version
// Time complexity: O(m+n), where m and n are the lengths of the two singly linked lists
// Space complexity: O(1)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    merged := dummyHead
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            merged.Next = list1
            list1 = list1.Next
        }else {
            merged.Next = list2
            list2 = list2.Next
        }
        merged = merged.Next
    }
    if list1 != nil {
        merged.Next = list1
    }
    if list2 != nil {
        merged.Next = list2
    }
    return dummyHead.Next
}

3.2. Recursion

// Time complexity: O(m+n)
// Space complexity: O(m+n); each recursive call occupies stack space, with up to m+n calls in the worst case
func Merge2(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
	if pHead1 == nil {
		return pHead2
	}
	if pHead2 == nil {
		return pHead1
	}

	if pHead1.Val < pHead2.Val {
		pHead1.Next = Merge2(pHead1.Next, pHead2)
		return pHead1
	} else {
		pHead2.Next = Merge2(pHead1, pHead2.Next)
		return pHead2
	}
}

4. References

• Merge Two Sorted Linked Lists - NowCoder
• 21. Merge Two Sorted Lists - LeetCode