链表(二)——链表的应用

2022-02-25 本文已影响0人东方胖

习题

有序链表的合并和交集
将两个有序的链表合并在一起
例子， L1: 1->2->4->5->7->9 ， L2: 0->2->3->6->8->10，合并后是
0->1->2->2->3->4->5->6->7->8->9->10

算法思路，L1 和 L2 都已经排好序，准备两个遍历指针 cur1, cur2 分别初始化在两个链表的起始处，如果 cur2.data < cur1.data 则将 cur2 插在 cur1的前面，否则 cur1 向右移动直到 cur1 比 cur2 的值更大。

整个过程像一个拉锯过程。如果 L1 遍历到底，L2 还有元素，把剩余的串头节点接在 L1 尾部即可；如果 L2 先遍历完，结束即可。
这个过程，每次插入操作时间代价是 O(1) ，时间复杂度的上界是 O(m + n), m, n 分别是两个链表的长度

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1

        cur1, cur2 = list1, list2 
        if list1.val > list2.val:
            cur1, cur2 = list2, list1
        head = cur1
        pre = None
        while cur1 and cur2:
            if cur1.val > cur2.val:
                tmp_node = cur2.next
                cur2.next = cur1
                pre.next = cur2
                pre = cur2
                cur2 = tmp_node
            elif cur1.val <= cur2.val:
                pre = cur1
                cur1 = cur1.next
        if cur2:
            pre.next = cur2

        return head

递归方案：
更加简洁的递归法

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        if list1.val >= list2.val:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2
        return None

有序链表的交集
计算两个有序链表中相同的元素。仍然以上面的例子为例，L1: 1->2->4->5->7->9 ， L2: 0->2->3->6->8->10 的交集只有一个元素 2；
对于无序数组我们取交集的办法一般是用哈希表统计两个表里的元素有哪些重复，用 O(m) 的时间建立一个 L1 每个元素出现频次的哈希表 h1，然后遍历 L2，当 L2 的元素出现在 L1 并且频次大于 0 时，我们将它取出存起来，并且将 h1 中该元素的频次减 1；
有序链表可以采用另一种方式，双迭代指针同时同 L1， L2 的头节点出发，然后比较当前两个链表的元素是否相等，相等则取出，不相同的话，比较小的那边向前走一个，大的那头不动，当其中一个链表遍历完时结束

链表的应用案例一——多项式的加法和乘法

多项式
$F(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0$
$Q(x) = b_mx^m + b_{m - 1}x^{m - 1} + ... + b_1x + b_0$
计算

$F + Q$
$F^p$
$F * Q$

考虑最简单的加法运算，我们只需要将次数相同的项的系数相加即可，常数项视为次数为 0 的项。假设我们用一个数组来表示多项式的系数，对于 $P(x)$ 而言，下标 0 处放常数项 $a_0$ ，下标 1 处是 $a_1$ , ... 下标 n 处是 $a_n$ , 任意的下标对应多项式该幂次的常数项。

这种方法是 ok 的，加法运算的法则就是，两个系数数组 $A_{n+1}$ 和 ${B_{m +1}}$ 逐项相加，更长的数组多出来的部分原样拷贝下来就行。

但是对于像 $x^{9999} + x + 1$ 和 $x ^ {4999} + 4x^{400} + 100$ 相加会出现什么问题？
系数数组大小分别是 10000 和 5000，大多数的计算是 0 + 0 ，由于不确定中间是不是有 400 次幂有 4 这样的系数，这些 0 的运算无法避免。同时，消耗了大量的内存空间，我们只是计算了两个看起来很简洁的多项式，如果多项式是 $x^{10000000}+1$ ，有更多的看起来没太大用处的 0 。

使用链表将会大大简化这种恶劣的情况。
将多项式的每一项抽象化为一个节点 Node

struct Node {
      CoeType coefficient; //系数
      int exp; //幂次
      Node* next;
}
typedef struct Node * Polynomial; // 表头

单链表按照多项式次数的降序顺序建立，从而多项式的加法转化为两个单链表的合并，与上面的习题一类似，唯一的区别是，我们对节点的值(幂次)相等的情况，要进行系数相加。
算法其它部分没有什么区别。
加法计算, 将上面的递归算法略加修改，代码如下：

Polynomial addTwoPolynomial(Polynomial p, Polynomial q)
{
    if (!p) {
        return q;
    }
    if (!q) {
        return p;
    }

    if (p-exp > q->exp) {
        p->next = addTwoPolynomial(p->next, q);
        return p;
    }
    if (p->exp < q->exp) {
        q->next = addTwoPolynomial(p, q->next);
        return q;
    }
    p->coefficient = p->coefficient + q->coefficient;
    p->next = addTwoPolynomial(p->next, q->next);
    return p;
}

乘法如何实现？两个单链表需要逐项相乘，各自长度为 m, n ，那么需要 m × n 次乘法，然后没有结束，我们还需合并同类项

链表(二)——链表的应用

习题

链表的应用案例一——多项式的加法和乘法

猜你喜欢

热点阅读