题目
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
python程序
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
_rootNode=ListNode(0)
rNode = _rootNode
while l1 and l2:
if l1.val<=l2.val:
rNode.next = ListNode(l1.val)
rNode = rNode.next
l1 = l1.next
else:
rNode.next = ListNode(l2.val)
rNode = rNode.next
l2 = l2.next
while l1:
rNode.next = ListNode(l1.val)
rNode = rNode.next
l1 = l1.next
while l2:
rNode.next = ListNode(l2.val)
rNode = rNode.next
l2 = l2.next
return _rootNode.next
这道题属于链表操作,最多需要遍历最长链表的长度。属于常规题目,但是链表的操作有一套定式,开始先声明头部,然而头部用两个变量来表示,因为链表的特性,你只能依次的回溯,不能直接跳到你想要的位置,所以用两个 变量,一个只是在最后返回的时候用,一次则参与主要运算。
while l1 and l2:
if l1.val<=l2.val:
rNode.next = ListNode(l1.val)
rNode = rNode.next
l1 = l1.next
else:
rNode.next = ListNode(l2.val)
rNode = rNode.next
l2 = l2.next
第一个循环,是算法的第一部分,因为两个链表的长度不一定相同,则这个循环会在短链表结束时停止,说明合并工作已经完成大部分了,接下来只需要将长链表的剩余部分接在合并的链表后面就行了,思路就是谁的值小我就加进合并的链表。
while l1:
rNode.next = ListNode(l1.val)
rNode = rNode.next
l1 = l1.next
while l2:
rNode.next = ListNode(l2.val)
rNode = rNode.next
l2 = l2.next
这里就是上面所说的将长链表剩余的添加进合并链表里面,因为从上面我们并不能得知哪个链表长,所以两个都要检查。