/

• 本题难度: Easy
• Topic: Linked List

Description

Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splicing together the nodes of the two lists and sorted in ascending order.

Example

Example 1:

Input: list1 = null, list2 = 0->3->3->null

Output: 0->3->3->null

Example 2:

Input: list1 = 1->3->8->11->15->null, list2 = 2->null

Output: 1->2->3->8->11->15->null

我的代码

"""Definition of ListNodeclass ListNode(object):    def __init__(self, val, next=None):        self.val = val        self.next = next"""class Solution:    """    @param l1: ListNode l1 is the head of the linked list    @param l2: ListNode l2 is the head of the linked list    @return: ListNode head of linked list    """    def mergeTwoLists(self, l1, l2):        # write your code here        if l1 is None:            return l2        if l2 is None:            return l1        res = pos = ListNode(0)        while(l1 and l2):            if l1.val 

思路

1. 之前没有仔细看过python的面向对象编程，因为Linked List中用到了定义新的类，所以简单看了一下教程：，写了笔记
2. 如果一开始就要决定新建第一个点的val，则需要和后面非常重复的判断条件，代码会很繁琐。借鉴了leetcode上的参考答案的思路，头结点仅用于建立链表，最后的结果舍弃掉头结点就好了。

• 时间复杂度 O(n)