21. Merge Two Sorted Lists

Question:

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Thinking:

• Basic Merge question.

	class Solution {
	    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
	        ListNode result = new ListNode(0);
	        ListNode head = result;
	        while(l1 != null || l2 != null){
	            if(l1 != null && l2 != null){
	                if(l1.val <= l2.val){
	                    result.next = l1;
	                    l1 = l1.next;
	                }else{
	                    result.next = l2;
	                    l2 = l2.next;
	                }
	                result = result.next;
	            }else if(l1 != null && l2 == null){
	                result.next = l1;
	                break;
	            }else{
	                result.next = l2;
	                break;
	            }
	        }
	        return head.next;
	    }
	}

二刷

二刷的时候犯了一个小错误，当c2或c1当c2或c1为null时只要直接append不为null的链表即可，不需要再一个个遍历。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode c1 = l1, c2 = l2, cur = dummy;
        while(c1 != null || c2 != null){
            if(c1 != null && c2 != null){
                if(c1.val < c2.val){
                    cur.next = c1;
                    c1 = c1.next;
                }else{
                    cur.next = c2;
                    c2 = c2.next;
                }
            }else if(c1 != null){
                cur.next = c1;
                break;
            }else{
                cur.next = c2;
                break;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

Amazon session

• Method 1: while loop ```Java /**
  • Definition for singly-linked list.
  • public class ListNode {
  • int val;
  • ListNode next;
  • ListNode(int x) { val = x; }

  • } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode t1 = l1, t2 = l2; ListNode cur = dummy; while(t1 != null && t2 != null){ cur.next = t1.val <= t2.val ? new ListNode(t1.val): new ListNode(t2.val); if(t1.val <= t2.val) t1 = t1.next; else t2 = t2.next; cur = cur.next; } cur.next = t1 != null ? t1: t2; return dummy.next; } } ```

  • Method 2: Recursion ```Java /**
  • Definition for singly-linked list.
  • public class ListNode {
  • int val;
  • ListNode next;
  • ListNode(int x) { val = x; }
  • } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null && l2 == null) return null; else if(l1 != null && l2 != null){ ListNode node = null; if(l1.val <= l2.val){ node = l1; ListNode next = mergeTwoLists(l1.next, l2); l1.next = next; }else{ node = l2; ListNode next = mergeTwoLists(l1, l2.next); l2.next = next; } return node; }else if(l1 != null) return l1; else return l2; } } ```