21、合并两个有序链表——LeetCode记录

问题描述

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

示例:

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
}

解法1-迭代法

思路

选择两个链表中的其中一个作为结果返回(命名为 i ),这就需要将另一个链表(命名为 j )中的结点 合理的插入到链表 i 中.

迭代执行,如果i.next.val大于等于j.val时,则将此时的 j 结点插入到 i 的next;否则,令i = i.next.

特殊情况判断

如果l1和l2同时为空,则返回NULL,如果有一个不为空,则返回另一个不为空的链表。

解法

定义两个指针ij,将i指向第一个结点数据较小的那个链表,j指向另一个链表。再定义一个L,令L=i,意为L指向i的头指针,最后将会返回L
依次遍历,如果i的下一个大于等于j,将结构体插入到inext;否则,j指向jnext
最后循环结束之后,将j之后的链表接到inext,返回i所指向的链表,即L

循环条件判断

因为需要获取i->next.valj.val比较,所以while循环中,当i.next != NULL && j != NULL,时,进入循环,否则跳出。
这时候,如果i.next != NULL时,证明链表j并未遍历完,所以需要再i的最后接上j的剩余部分。

代码

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if (l1 == NULL || l2 == NULL){
        return (l1 == NULL&&l2 == NULL)? NULL:(l1 == NULL)? l2:l1;
    }
    struct ListNode *i, *j;
    i = l1->val <= l2->val ? l1:l2;
    j = (i == l1) ? l2:l1;
    struct ListNode *L = i;
    while (i->next != NULL && j != NULL){
        if (i->val <= j->val && j->val < i->next->val){
            //临时指针
            struct ListNode *x = j->next;
            j->next = i->next;
            i->next = j;
            j = x;
        }
            i = i->next;
    }
    if (i->next == NULL)
        i->next = j;
    return L;
}

时间复杂度为O(m+n),空间复杂度为O(0),没有使用额外的空间。

官网还有一种类似的解法,是依次将较小的那个结点连接起来(串起来)再返回,和我这个基本类似,具体实现有一些微小的差异,感兴趣的可以去看看,合并两个有序链表

解法二——递归

这种解法真的很神奇,虽然书上说递归符合人类的思考习惯,但是要真正理解程序中的执行情况还是有点难度的。这里使用python,可读性较高。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        else:
            if l1.val < l2.val:
                l1.next = self.mergeTwoLists(l1.next,l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1,l2.next)
                return l2

思路

简单来说,就是比较后面剩余的两个链表,将较小的那个结点穿起来(连接起来),直到某一个链表为空,则返回另一个链表剩余的部分。重复执行 这个动作,即为递归。公式如下:

这样,用python实现最为简单已读,不过用C也是可以实现的。

时间复杂度为O(m+n),空间复杂度为递归栈的深度O(m+n)。

总结

有一些看似更好的代码,但实际上仅仅只是利用了一些编程语言的特性。比如同样使用递归的这个例子:

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val: l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1 or l2

备注: 在 Python 中,and 和 or 都有提前截至运算的功能。

and:如果 and 前面的表达式已经为 False,那么 and 之后的表达式将被 跳过,返回左表达式结果
or:如果 or 前面的表达式已经为 True,那么 or 之后的表达式将被跳过,直接返回左表达式的结果
例子:[] and 7 等于 []

这段代码的功能和上面的那个完全相同,时间和空间复杂度并几乎没有改善。虽然看着简洁,但是失去了代码的可读性,未来在修改的时候也将会花费更大的精力。

所以,我们要为了提升代码的时间和空间复杂度而努力,不是为了哗众取宠,降低代码的可读性。