public class Main {

    /**
     * Given two sorted linked lists, return a single merged sorted list
     *
     * Input: 
     * l1 = 1->1->5
     * l2 = 2->6 
     * 
     * Return: 1->1->2->5->6
     */

    public static void main(String[] args) {
        // 1->5
        ListNode n1 = new ListNode(1, new ListNode(5));
        
        // 2->6
        ListNode n2 = new ListNode(2, new ListNode(6));
        
        // 1->2->5->6
        ListNode answer_n1 = new ListNode(1, new ListNode(2, new ListNode(5, new ListNode(6))));

        ListNode mergedList = mergeTwoLists(n1, n2);
        System.out.println("Test case 1 passed: " + answer_n1.equals(mergedList));
    }
    
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode dummyNode = new ListNode(1);
        
        ListNode currentTail = dummyNode;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                currentTail.next = l1;
                l1 = l1.next;
                
            } else {  
                currentTail.next = l2;
                l2 = l2.next;
            }
            
            currentTail = currentTail.next;
        }
        
        return dummyNode.next;
    }
    
    public static class ListNode {
      int data;
      ListNode next;

      ListNode(int data) {
          this.data = data;
      }

      ListNode(int data, ListNode next) {
          this.data = data;
          this.next = next;
      }
    }
}