LeetCode - Merge Two Sorted Lists | Darren's Blog

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        // Handling special cases

        if (l1 == null)

            return l2;

        if (l2 == null)

            return l1;

        ListNode head = new ListNode(0), p = head;  // Use a header node to avoid boundary check

        // Merge two non-empty list

        while (l1 != null && l2 != null) {

            if (l1.val <= l2.val) {     // The current node in the first list is smaller

                p.next = l1;

                l1 = l1.next;

            } else {            // The current node in the second list is smaller

                p.next = l2;

                l2 = l2.next;

            }

            p = p.next;     // Move p to the end of the merged list

        }

        // The first list has remaining nodes while the second has none

        while (l1 != null) {

            p.next = l1;

            l1 = l1.next;

            p = p.next;

        }

        // The second list has remaining nodes while the first has none

        while (l2 != null) {

            p.next = l2;

            l2 = l2.next;

            p = p.next;

        }

        // Return the merged list without the header

        return head.next;

    }

Read full article from LeetCode - Merge Two Sorted Lists | Darren's Blog