LeetCode 21.合并两个有序链表

LeetCode 21.合并两个有序链表

这道题的LeetCode编号是 21,各位可以自行去LeetCode网站练习。

题目描述

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

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

题解

按照题目的要求,最终要把L1和L2两个链表合并成一个链表,实例图如下

我们要注意一种特殊的情况,链表L1为空,或者链表L2也为空,甚至L1和L2都是空
在面试的时候,碰到这种题目,第一时间在函数的入口处把边界条件处理了。
比如加上下面这段:

class Solution {
	public ListNode mergeTwoLists(ListNode L1, ListNode L2) {
		if(L1==null) {
			if(L2==null) {
				return null;
			} else {
				return L2;
			}
		} else {
			if(L1==null) {
				return null;
			} else {
				return L1;
			}
		}
		//...
	}
}	
                                                                             

上面的代码只是实例,实际不用这么麻烦,用个三目表达式就可以搞定了

class Solution {
	public ListNode mergeTwoLists(ListNode L1, ListNode L2) {
		//如果L1,L2有一个为空,直接返回就可以了
		//如果L1为空,返回L2(如果此时L2也是空就返回null)
		//如果L2不为空就返回L1
		if(L1==null || L2==null) {
			return (L1==null)? L2 : L1;
		}
		//...
	}	
} 
                                                                         

python的代码如下:

class Solution(object):
	def mergeTwoLists(self, l1, l2):
		"""
		:type l1: ListNode
		:type l2: ListNode
		:rtype: ListNode
		"""
		if not (l1 and l2):
			return l1 if l1 else l2
	#...
                                                        

示例中的L1和L2两个链表一样长,但我们也要考虑到另外一种场景,L1和L2不一样长

这种情况也好办,我们在合并链表的时候,就假设L1和L2是一样长的。等合并完之后,要不L1和L2都为空,
要不就是L1和L2中的某一个不为空,我们只需要将合并完的链表尾巴指向那个不为空的L1或者L2就可以了

动态示例如下:

代码如下:

class Solution(object):
	def mergeTwoLists(self, l1, l2):
		"""
		:type l1: ListNode
		:type l2: ListNode
		:rtype: ListNode
		"""
		#增加一个冗余的节点,方便后续处理
		p = ListNode(-1)
		head = p
		#这里的意思是l1!=null && l2!=null
		while l1 and l2:
			#如果l1的val<=l2的val,就将p指向l1
			#p.next,l1 = l1,l1.next这里是将两行合并了
			#只是为了代码简洁,面试时如果没有十足把握尽量分多行写
			if l1.val<=l2.val:
				p.next,l1 = l1,l1.next
			#else时,将p指向l2节点
			else:
				p.next,l2 = l2,l2.next
			p = p.next
		#这里是一个三目表达式,类似
		# l1==null? l2:l1 
		# 如果l1不为空就将p.next指向l2
		# 如果l1为空就指向l2,如果l2也为空那就指向空
		p.next = l1 if l1 else l2
		return head.next
                                                                              

递归版本

对于这道题,还有一个更骚气的递归解法,用递归的话,难度就陡增了,如果没有十足的把握尽量不要用递归,用上面那种迭代版本就可以了。
递归的动态图如下:

代码如下

class Solution(object):
	def mergeTwoLists(self, l1, l2):
		"""
		:type l1: ListNode
		:type l2: ListNode
		:rtype: ListNode
		"""
		#递归的结束点就是L1或者L2为空就返回
		#如果L1为空就返回L2,L2为空返回L1
		if not (l1 and l2):
			return l1 if l1 else l2
		#L1的val<=L2的val,那么继续递归
		#当前L1的next指向一个递归函数
		#意思是L1的下一个和L2哪个大,就作为当前L1的next
		if l1.val<=l2.val:
			l1.next = self.mergeTwoLists(l1.next,l2)
			return l1
		else:
			l2.next = self.mergeTwoLists(l1,l2.next)
			return l2	
                                                                            
(全文完)
2 次阅读

发表评论

电子邮件地址不会被公开。