L1-合并两个排序链表

Posted on | In |

合并两个排序链表
将两个排序链表合并为一个新的排序链表

样例
给出 1->3->8->11->15->null，2->null， 返回 1->2->3->8->11->15->null。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
"""
Definition of ListNode
class 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 == None:
            return l2
        if l2==None:
            return l1
        if l1 == None and l2 == None:
            return None
        head=ListNode(0)
        cur=head
        while l1!=None and l2!=None:
            if l1!=None and l2!=None:
                if l1.val<l2.val:
                    cur.next=l1
                    cur=cur.next
                    l1=l1.next
                else:
                    cur.next=l2
                    cur=cur.next
                    l2=l2.next
            if l1==None:
                cur.next=l2
                break
            if l2==None:
                cur.next = l1
                break
        return head.next

思路

异步的方式移动两个链表的指针，时间复杂度O(n+m)

参考链接
http://www.cnblogs.com/theskulls/p/4870694.html