21 Merge Two Sorted Lists – Easy¶

Problem:¶

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.

Thoughts:¶

This is a very straightforward problem. Using a fakeHead pointer is solving a lot of troubles in many list problems. For this problem, you don’t have to use it. You could also solve the problem without using it.

Solutions:¶

/**
* Definition for singly-linked list.
* public class ListNode {
*         int val;
*         ListNode next;
*         ListNode(int x) {
*                 val = x;
*                 next = null;
*         }
* }
*/
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode fakeNode = new ListNode(-1);
        ListNode node = fakeNode;
        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                node.next = l1;
                l1 = l1.next;
                node = node.next;
            }//if
            else{
                node.next = l2;
                l2 = l2.next;
                node = node.next;
             }//else
        }//while l1 & l2
        if (l1 != null){
            node.next = l1;
        }
        else if (l2 != null){
            node.next = l2;
        }
        return fakeNode.next;
    }
}