Cd73a58d1d414c2403211d4cd269a6a8
(难度等级Easy)Problem 21: Merge Two Sorted Lists(有序链表归并)

Problem 21: Merge Two Sorted Lists(有序链表归并)

链接

https://leetcode.com/problems/merge-two-sorted-lists/

难度等级

Easy

题干

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.

题意

给定两个有序链表,将这两个按大小顺序合并成一个链表,返回这个链表

样例

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

题解

这道题难度是Easy,的确不难,基本上所有的难度都在编码上。

由于这两个链表已经是有序的,所以只需要对链表做一个归并操作即可。也就是说用两个指针分别指向这两个链表的头结点,永远拿取两个链表当中比较小的元素。

伪代码如下:

def merge(listA, listB):
    h1 = listA.head()
    h2 = listB.head()
    h = new List()
    while h1 != None or h2 != None:
        if h1 < h2:
            h.append(h1)
        else:
            h.append(h2)
        h1 = h1->next
        h2 = h2->next
    return h

这里没有考虑两个链表当中有一个中的元素较小提前到了末尾的情况,如果发生也很简单。只需要加入判断链表当中是否有空的逻辑,如果有空,默认选择另一个链表的元素即可。

top Created with Sketch.