[简单]合并两个有序链表

原创
2019/09/06 23:25
阅读数 105

一、题目(这是一道之前川农研究生入学考试复试的一道题还是初试的一道题,差不多就这难度了....)

 

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

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-two-sorted-lists
 

二、解答

1.算法思路

    这道题思路比较好想,有很多种解决方案:

        【1】 选择一条主表,选择一条从表,循环遍历从表,将从表的元素按照大小插入主表,最后返回主表即可。

        【2】 使用两个指针,用来分别遍历两个链表,将两个表的元素较小者插入答案链表,直到两个指针都为空为止,最后返回答案链表

    由于第一种在写的时候没写好遇到边界问题,只有20分钟时间,放弃了,重新写了第二个。

2.代码

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        r = ListNode(0)
        ans = r
        len1 = 0
        len2 = 0
        p = l1
        q = l2
        while p != None:
            len1 += 1
            p = p.next
        while q != None:
            len2 += 1
            q = q.next
        p = l1
        q = l2
        while p != None or q != None:
            if p == None:
                r.next = q
                break
            elif q == None:
                r.next = p
                break
            else:
                r.next = ListNode(0)
                r = r.next
            if p.val >= q.val:
                r.val = q.val
                q = q.next
            else:
                r.val = p.val
                p = p.next
        return ans.next

3.运行结果

提交几次,最快一次52ms

 

4.总结

这是一道简单的链表算法题,只要明白链表的结构,就相当简单。没有什么算法思想。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部