1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 25 题] “合并两个排序的链表”做题记录

[剑指 Offer 第 2 版第 25 题] “合并两个排序的链表”做题记录

第 25 题:合并排序的链表

传送门:AcWing:合并两个排序的链表牛客网 online judge 地址

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

样例:

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

输出:1->2->3->4->5->5

分析:同 LeetCode 第 21 题,传送门:21. 合并两个有序链表。这是一道经典的问题,可以使用“穿针引线”,也可以使用递归求解,个人觉得递归的代码比较简洁易懂。“穿针引线”则要画图。

思路1: 使用递归,编码简单。

Python 代码:

  # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None


    class Solution(object):
        def merge(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """

            if l1 is None:
                return l2
            if l2 is None:
                return l1

            # 代码能走到这里说明 l1 和 l2 均非空
            # 比较哪个小就行了
            if l1.val < l2.val:
                l1.next = self.merge(l1.next, l2)
                return l1
            # 走到这里 l1.val >= l2.val
            l2.next = self.merge(l1, l2.next)
            return l2

Java 代码:

  class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public class Solution {
        public ListNode Merge(ListNode list1, ListNode list2) {
            if (list1 == null) {
                return list2;
            }
            if (list2 == null) {
                return list1;
            }
            if (list1.val < list2.val) {
                list1.next = Merge(list1.next, list2);
                return list1;
            } else {
                list2.next = Merge(list1, list2.next);
                return list2;
            }
        }
    }

思路2:穿针引线。

liwei201910119_1.png

liwei201910113_2.png

Python 代码:

  # Definition for singly-linked list.
    class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None


    # 穿针引线的写法,一定要画图才能写出来
    # 比较麻烦,还是递归处理简单

    class Solution(object):
        def merge(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            # 引入头结点可以简化对问题的讨论
            dummy_node = ListNode(-1)
            cur_node = dummy_node
            p1 = l1
            p2 = l2

            while p1 and p2:
                # 两者都不为空,才须要比较
                # 其中有一个为空的时候,把其中一个接到另一个尾巴就好了
                if p1.val < p2.val:
                    # next 指针修改
                    cur_node.next = p1
                    # p1 后移
                    p1 = p1.next
                else:
                    cur_node.next = p2
                    p2 = p2.next
                cur_node = cur_node.next
            # 跳出循环的时候,一定有:p1 为空或者 p2 为空
            # 其中有一个为空的时候,把其中一个接到另一个尾巴就好了
            if p1 is None:  # 这一句写成 if not p1 也是可以的,不过不好理解
                cur_node.next = p2
            if not p2:
                cur_node.next = p1
            return dummy_node.next

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 25 题] “合并两个排序的链表”做题记录

链接:https://www.javajike.com/article/3274.html

« [剑指 Offer 第 2 版第 24 题] “反转链表”做题记录
[剑指 Offer 第 2 版第 27 题] “二叉树的镜像”做题记录»

相关推荐

QR code