21. 合并两个有序链表

转载自Leet Code

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。 新链表是通过拼接给定的两个链表的所有节点组成的。 

示例： >输入：1->2->4, 1->3->4 >输出：1->1->2->3->4->4 ---

我的代码

\(T(M,N) = O(M+N)\), \(S(M,N) = O(M+N)\)

{.line-numbers}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class MySolution21 
{
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) 
    {
    	ListNode newList = null;
    	ListNode p = null;
    	
        ListNode p1 = l1; ListNode p2 = l2;
        while (p1!=null&&p2!=null)
        {
        	int val1 = p1.val; int val2 = p2.val;
        	
        	if (val1<val2)
        	{
        		if (newList==null)
        		{
        			newList = new ListNode(val1,null);
        			p = newList;
        		}
        		else
        		{
        			ListNode newNode = new ListNode(val1,null);
        			p.next = newNode;
        			p = newNode;
        		}
        		p1 = p1.next;
        	}
        	else
        	{
        		if (newList==null)
        		{
        			newList = new ListNode(val2,null);
        			p = newList;
        		}
        		else
        		{
        			ListNode newNode = new ListNode(val2,null);
        			p.next = newNode;
        			p = newNode;
        		}
        		p2 = p2.next;
        	}
        }
        
        while (p1!=null)
        {
    		if (newList==null)
    		{
    			newList = new ListNode(p1.val,null);
    			p = newList;
    		}
    		else
    		{
    			ListNode newNode = new ListNode(p1.val,null);
    			p.next = newNode;
    			p = newNode;
    		}
    		p1 = p1.next;
        }
        while (p2!=null)
        {
    		if (newList==null)
    		{
    			newList = new ListNode(p2.val,null);
    			p = newList;
    		}
    		else
    		{
    			ListNode newNode = new ListNode(p2.val,null);
    			p.next = newNode;
    			p = newNode;
    		}
    		p2 = p2.next;
        }
        return newList;
    }
}

方法一：递归

\(T(M+N) = O(M+N)\), \(S(M+N) = O(M+N)\)

可以递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）， 即链表头中较小的那个节点与剩下元素的 merge 操作结果合并： \[ \begin{cases} list1[0]+merge(list1[1:],list2), &if\ list[0] < list2[0]\\ list2[0]+merge(list1,list2[1:]), &otherwise \end{cases} \]

将以上递归过程建模，并且考虑边界情况： 如果l1或者l2一开始就是空链表，那么没有任何操作需要合并，返回非空链表即可； 否则，需要判断l1和l2哪一个链表的头节点更小，然后递归地决定下一个添加到结果中的节点， 若两个链表中有一个为空则递归结束。

{.line-numbers}

class Solution21
{
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) 
	{
		if (l1 == null)  return l2;
		if (l2 == null)  return l1;
		
		if (l1.val < l2.val) 
		{
		    l1.next = mergeTwoLists(l1.next, l2);
		    return l1;
		} 
		else 
		{
		    l2.next = mergeTwoLists(l1, l2.next);
		    return l2;
		}
	}
}

方法二：迭代

\(T(M+N) = O(M+N)\), \(S(M+N) = O(1)\)

利用哑节点prevNode和前置指针prev，不需要创建额外的新链表。

{.line-numbers}

class Solution21
{
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) 
	{
		ListNode prevNode = new ListNode(-1, null);
		ListNode prev = prevNode;
		
		while (l1!=null&&l2!=null)
		{
			if (l1.val<l2.val)
			{
				prev.next = l1;
				l1 = l1.next;
			}
			else 
			{
				prev.next = l2;
				l2 = l2.next;
			}
			prev = prev.next;
		}
		
		if (l1!=null) prev.next = l1;
		else prev.next = l2;
		
		return prevNode.next;
	}
}