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	
                                                                            
(全文完)
18 次阅读

6 thoughts on “LeetCode 21.合并两个有序链表

  1. Здесь вы можете заказать копию любого сайта под ключ, недорого и качественно, при этом не тратя свое время на различные программы и фриланс-сервисы.

    Клонированию подлежат сайты как на конструкторах, так и на движках:
    – Tilda (Тильда)
    – Wix (Викс)
    – Joomla (Джумла)
    – WordPress (Вордпресс)
    – Bitrix (Битрикс)
    и т.д.
    телефон 8-996-725-20-75 звоните пишите viber watsapp
    Копируются не только одностраничные сайты на подобии Landing Page, но и многостраничные. Создается полная копия сайта и настраиваются формы для отправки заявок и сообщений. Кроме того, подключается админка (админ панель), позволяющая редактировать код сайта, изменять текст, загружать изображения и документы.

    Здесь вы получите весь комплекс услуг по копированию, разработке и продвижению сайта в Яндексе и Google.

    Хотите узнать сколько стоит сделать копию сайта?
    напишите нам
    8-996-725-20-75 звоните пишите viber watsapp

    Here you can order a copy of any site turnkey, inexpensive and high quality, while not wasting your time on various programs and freelance services.

    Cloning sites are subject to both designers and engines:
    – Tilda (Tilda)
    – Wix (Wicks)
    – Joomla (Joomla)
    – WordPress (WordPress)
    – Bitrix (Bitrix)
    etc.
    phone 8-996-725-20-75 call write viber watsapp
    Not only single-page sites like Landing Page are copied, but also multi-page sites. A full copy of the site is created and forms for sending requests and messages are set up. In addition, the admin panel is connected, which allows you to edit the site code, change the text, upload images and documents.

    Here you will get a full range of services for copying, development and promotion of the site in Yandex and Google.

    Do you want to know how much it costs to make a copy of the site?
    write to us
    8-996-725-20-75 call write viber watsapp

发表评论

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