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

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. 没有仔细分析题目,题目描述中给的一些隐藏条件都没提取出来,便开始着手编写代码
  2. 过于执着于链表有无头结点的处理模式,导致编写出来的函数适用性很差
21.合并有序链表 - (链表)21.合并有序链表 - (链表) 时夜斗 发布了1 篇原创文章 · 获赞 0 · 访问量 26 私信 关注
上一篇:[解题报告]《算法零基础100讲》(第17讲) 线性枚举(一) - 最值算法(1)(2)


下一篇:两数之和I