leetcode[21]-合并两个有序链表

题目

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

示例：

输入：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

这里就是上面所说的将长链表剩余的添加进合并链表里面，因为从上面我们并不能得知哪个链表长，所以两个都要检查。