21. Merge Two Sorted Lists.md

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;
    }
}

Third Time

• Method 1: Basic list question

   /**
    * 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), cur = dummy;
   		while(l1 != null || l2 != null){
   			if(l1 != null && l2 != null){
   				cur.next = l1.val < l2.val ? l1: l2;
   				if(l1.val < l2.val) l1 = l1.next;
   				else l2 = l2.next;
   			}else if(l1 != null){
   				cur.next = l1;
   				l1 = l1.next;
   			}else{
   				cur.next = l2;
   				l2 = l2.next;
   			}
   			cur = cur.next;
   		}
   		return dummy.next;
   	}
   }