0%

[0021] 合并两个有序链表

发表于 更新于 分类于 ， 本文字数： 1.7k 阅读时长 ≈ 2 分钟
...

[0021] 合并两个有序链表

题目描述

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

示例：

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

Related Topics
  • 链表

    • 题目解析

    • 本题是一道模拟题

    不确定性

    方法一：顺序迭代法

    分析

    • 分别从l1和l2的第一个节点进行比较，将小的拿出来放在前面
    • 若有其中一个链表的所有节点都被取完了，则将另一个链表中未被取出的所有的节点顺序添加到后面

    思路

    • 建立一个新的链表，使用指针t指向新链表的表头
    • 使用l1和l2两个指针，遍历给出的链表
    • 若l1所指向节点的值小于l2所指向节点的值，则将l1放在t所指向节点之后，反之则将l2放在t所指向节点之后
    • 当l1和l2链表中有一个链表遍历完后，则将另一个链表的剩余节点都顺序添加到t所指向节点的后面

    注意

    知识点

    • 链表的遍历

    复杂度

    • 时间复杂度 O(m+n)，其中m为l1的长度，n为l2的长度
    • 空间复杂度 O(1)

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    	ListNode* head = new ListNode(0);
    	ListNode* t = head;

    	while (l1 && l2){
    		if (l1->val < l2->val){
    			t->next = l1;
    			l1 = l1->next;
    		}
    		else{
    			t->next = l2;
    			l2 = l2->next;
    		}
    		t = t->next;
    	}
    	if (l1){
    		t->next = l1;
    	}
    	if (l2){
    		t->next = l2;
    	}
    	return head->next;
    }

    方法二：递归法

    分析

    • 合并时每次的操作是一致的：将两个链表中最小的节点拿出来，再用相同的规则合并剩余的两个链表

    思路

    • 判断l1和l2所指向节点的值哪一个更小，然后递归地决定下一个添加到结果里的值
    • 当递归完其中某一个链表时，则返回另一个链表剩余的节点

    注意

    • 边界情况的处理，当l1或l2为空链表时，则返回另一个链表剩余的节点

    知识点

    • 递归

    复杂度

    • 时间复杂度 O(m+n)，其中m为l1的长度，n为l2的长度
    • 空间复杂度 O(m+n)，其中m为l1的长度，n为l2的长度

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    	if (!l1){
    		return l2;
    	}
    	if (!l2){
    		return l1;
    	}
    	if (l1->val < l2->val){
    		l1->next = mergeTwoLists(l1->next, l2);
    		return l1;
    	}
    	else{
    		l2->next = mergeTwoLists(l1, l2->next);
    		return l2;
    	}
    }

    相关题目

    相关文章