21.合并有序链表 - （链表）

2024-02-01 20:40:16

21.合并有序链表 - (链表)

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

示例：

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

代码：

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

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL)
        return l2;
    if (l2 == NULL) 
        return l1;
    
    if (l1->val >= l2->val) {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    } else {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
}

执行代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node * next;
} Node;
typedef struct Node * ListNode;

void ShowList(LinkList point);
LinkList mergeTwoLists(LinkList l1, LinkList l2);
void CreateLink(LinkList list, int ch[], int n);

int main(void) {
    LinkList Heada, Headb, point;
    int cha[] = {1, 2, 3};
    int chb[] = {3, 4, 4};

    // 包含头指针的链表...
    Heada = (LinkList) malloc(sizeof(Node));
    Headb = (LinkList) malloc(sizeof(Node));
    point = Heada;
    CreateLink(point, cha, 3);
    ShowList(Heada->next);
    point = Headb;
    CreateLink(point, chb, 3);
    ShowList(Headb->next);

    // unite...
    point = mergeTwoLists(Heada->next, Headb->next);
    ShowList(point);

    return 0;
}

/* 输出显示每条链表 */
void ShowList(LinkList point) {
    while (1) {
        printf("%d", point->value);
        
        if (point->next == NULL)
            break;
        printf("->");
        point = point->next;
    }
    printf("\n");
}

/* 合并两条链表的函数 */
LinkList mergeTwoLists(LinkList l1, LinkList l2) {
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;


    if (l1->value >= l2->value) {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    } else if (l1->value < l2->value) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
}

/* 循环创建链表节点 */
void CreateLink(LinkList list, int ch[], int n) {
    if (list == NULL) {
        printf("LinkList == NULL...\n");
        return;
    }

    LinkList point = list;
    for (int i = 0; i < n; i++) {
        // create New Node...
        LinkList p = (LinkList) malloc(sizeof(Node));
        p->next = NULL;
        p->value = ch[i];
        // link the Node...
        point->next = p;
        point = p;
    }
}

解题分析：

题意上说是，将已经处于有序状态的两条链表重新合并成一条有序链表
- A (有序链) + B (有序链) = C (有序链)
- 本质上就是：排序！既然是 “排序”，那么基本的操作方式便是：“比较”
不过由于前提条件中，两条待合并的链表都是有序链，所以，比较的过程会简化很多
- 为什么这样说呢，是因为，这种情况下，只是两条链表之间的顺序是未知的而已
- 只要 A 链表中的 a 元素的值大于 B 链表中的 b 元素的值，那么前者中那些位于 a 元素之后的那些元素肯定也是大于 b 元素的。毫无疑问，单个链表是按照从小到大，还是从大到小，从示例中可以看出：1->2->3，很明显是从小到大。这也减少了，我们再对同一条链表进行比较的步骤（简便+1)。在这种已经知道了，A 链的后续是肯定比 b 元素的值大的情况下，我们又可以减去 A 链后续元素的比较任务（简便+1）
设计比较方式：
- 从上面的分析，我们可以知道，现在的比较只需要考虑不同链之间的比较。
- 具体的比较描述便是：将两条链分别设定为 A B 链，默认选择 A 链的最小元素（最低元素）跟 B 链的最小元素进行比较。如果 a 大于或等于 b ，那么下面我们需要做的就是看看位于 b 之后的元素与 a 的大小关系。如果 a 小于 b，那我们需要看的便是位于 a 之后的元素与 b 的大小关系。这一过程便是整个比较过程的一个小循环，当上面的比较过程结束后，我们就可以确定出一个节点在合并后的链表中的绝对位置。
- 如果将合并链表的整个过程看做是"母过程"，那么上面描述的比较过程，则是"子过程"。N 个子过程 = 整个母过程。因为最后我们要行成的是一条链表，所以，在每次的子过程结束后，都要确定与当前节点相连的下一个节点。但由于单链表的特性，我们只能选择从前向后的进行比较，也就是说，当我们比较当前节点的情况下，是无法确定后续节点的。因为按照先后性来说，我们是无法确定后面还未发生的事情，正如我们在现在说出未来将要发生的事情一样。但是 coding 是魔法的世界，这里有一种可以实现未来的回溯，预测未来的咒语——递归。
- 设计递归：因为整个母过程 = N 个子过程，所以整个比较过程就是不断的重复循环子过程的比较过程。另外，我们需要知道，依次对每个节点进行比较的过程就是子过程。根据这些分析，我们可以确定出递归函数的作用区间是：对等比较的两条链表的不同节点；工作原理是：先确定出两个节点的大小关系，再由确定它们的后续节点，这一步则由大小比较中值大的跟值小的节点的后续节点进行比较，在这轮比较中，值大者进入下一轮的对等比较，值小者作为上一轮对等比较的后续连接节点。循环往复，直到进行到对等比较中的一方节点为 “NULL” 时，整个递归开始回溯，最后，结束。
  - 这里，我们需要抽象几个逻辑步骤。
    1.对等比较：每次的节点比较都是为了确定出的两个节点的大小关系，依次来确定出。
    2.值小的作为上一级的后续链接节点：简单的伪代码表示则是，return 值小的节点。
    3.值大者加入下一级的对等比较：指代递归，伪代码表示：a > b { fun(a, b->next) } || b < a {fun(a->next, b)}
    4.整个递归回：因为进行到存在 “NULL” 节点，意味着有链表走到尽头了，根据前面的分析，另外一条链表的后续值肯定都是大于走到尽头的链表的，所以，直接 return。出现 return，即意味着递归的下潜结束，回溯开始。

我踩到的坑：

没有仔细分析题目，题目描述中给的一些隐藏条件都没提取出来，便开始着手编写代码
过于执着于链表有无头结点的处理模式，导致编写出来的函数适用性很差

时夜斗发布了1 篇原创文章 · 获赞 0 · 访问量 26 私信关注

码农公寓

21.合并有序链表 - (链表)

相关文章