微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 25.合并两个排序的链表

剑指offer 25.合并两个排序的链表

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

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

限制：

0 <= 链表长度 <= 1000

题解

(二路归并) O(n)

新建一个虚拟头节点 dummy 用于存储合并两个链表后的新链表 根据归并的思想，两个指针 l1 和 l2 分别指向两个链表

  1. 当 l1 和 l2 不为空时，循环比较两个指针指向节点的值的大小
  2. 如果 l1->val < l2->val，把 l1 节点拿出来放到新链表的末尾，同时 l1 往后移
  3. 如果 l1->val >= l2->val，把 l2 节点拿出来放到新链表的末尾，同时 l2 往后移
  4. l1 和 l2 只要有一个为空循环结束，肯定有一个为空，另一个不为空，最后需要将不为空的部分接到新链表的末尾
  5. 返回虚拟节点的 next 就是新链表的真正头节点

时间复杂度

两个链表各遍历一次，所以总时间复杂度为 O(n)

空间复杂度

O(n)，n 为两个链表的长度之和

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) cur->next = l1, l1 = l1->next, cur = cur->next;
            else cur->next = l2, l2 = l2->next, cur = cur->next; 
        }

        if (l1) cur->next = l1;
        if (l2) cur->next = l2;

        return dummy->next;
    }
};

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }

        return dummy.next;
    }
}

Python 代码

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

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(-1)
        cur = dummy
        
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next

        if l1:
            cur.next = l1
        if l2:
            cur.next = l2

        return dummy.next

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer