LeetCode -- Merge Two sorted lists

LeetCode -- Merge Two sorted lists

題目描述：
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.


就是把兩個已經排序的鏈表進行合並。


思路：
將鏈表l2合並到l1中，逐個遍歷l2
如果l1不是最後一個:
l1<=l2 && l2 <= l1.next ：移除l2，將l2放在l1.next
l2 < l1 : 將l2.next=l1 並替換頭結點
else: l1=l1.next
如果l1是最後結點：
l2 > l1：l1.next = l2
else : 將l2.next = l1並替換頭結點




實現代碼：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
    	if(l1 == null){
		return l2;
	}
	if(l2 == null){
		return l1;
	}
	
	// merge l2 into l1
	ListNode head = l1;
	while(l2 != null){
		if(l1.next != null){
			if(l2.val >= l1.val && l2.val <= l1.next.val){
				var t = Remove(ref l2);
				t.next = l1.next;
				l1.next = t;
			}
			else if(l2.val < l1.val){
				var t = Remove(ref l2);
				t.next = l1;
				
				head = t;
				l1 = t;
			}
			else{
				l1 = l1.next;
			}
		}
		else{
			if(l1.val < l2.val){
				l1.next = Remove(ref l2);
			}
			else{
				var t = Remove(ref l2);
				t.next = l1;
				
				head = t;
				l1 = t;
			}
		}
		
	}
	
	return head;
    }
    
    private ListNode Remove(ref ListNode n)
    {
        
    	ListNode t = new ListNode(n.val);
    	if(n.next == null){
    		n = null;
    	}
    	else{
    		n.val = n.next.val;
    		n.next = n.next.next;
    	}
    	return t;
    }


}