Leetcode(21) Merge Two Sorted Lists

发表于 | 更新于 | 分类于

Description:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

解法：

新建一个链表，然后比较两个链表中的元素值，把较小的那个链到新链表中，由于两个输入链表的长度可能不同，所以最终会有一个链表先完成插入所有元素，则直接另一个未完成的链表直接链入新链表的末尾。代码如下：

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
# Definition for singly-linked list.
class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        p = l1;
        q = l2;
        result = ListNode(-1);
        x = result;
        while(p!= None and q != None):
            if(p.val < q.val):
                tmp = ListNode(p.val);
                x.next = tmp;
                p = p.next;
                x = x.next; 
            else:
                tmp = ListNode(q.val);
                x.next = tmp;
                q = q.next;
                x = x.next;
        if(p != None):
            x.next = p;
        else:
            x.next = q;
        result = result.next;
        return result;