题目要求

本题要求实现一个函数,将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义:

List Merge( List L1, List L2 );

其中 List 结构定义如下:

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L1 和 L2 是给定的带头结点的单链表,其结点存储的数据是递增有序的;函数 Merge 要将 L1 和 L2 合并为一个非递减的整数序列。应直接使用原序列中的结点,返回归并后的带头结点的链表头指针。

裁判测试程序样例:

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

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表;空链表将输出 NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例:

3
1 3 5
5
2 4 6 8 10

输出样例:

1 2 3 4 5 6 8 10
NULL
NULL

我犯的错误

今天从 16 点开始做,一直做到 21 点多,一直调试不出来,然后最后看了别人写的代码,一通百通了。才知道自己今天犯了多少蠢。现在来复盘一下自己今天的学习。

没有审题

今天看题目没有看仔细,所以一直遗漏了下面这些要点:

  1. 题目中的链表是有首前节点的,但是我没有意识到这个

  2. 没有考虑到空链表的情况

  3. 没有考虑到题目需要的是将 L1 与 L2 置空。

没有打草稿

我没有打草稿,因此做了这么久。我应该开始的时候列出所有要考虑到的情况,比如两个链表都是空的的情况。而且这个过程要在脑子里面有一个过程的图画。

我的解答

代码

  /* Return a pointer to a non-decrease List.
   * - 2021-04-30 6:00 pm: I give up to find an elegant solvation. */
  List Merge( List L1, List L2 ) {
      /* Not null list */
      if (L2->Next == NULL) return L1;
      if (L1->Next == NULL) return L2;  // condition 1

      List R = malloc(sizeof (struct Node));
      List p = L1;

      while (L2->Next != NULL) { // until L2 run out
          if (p->Next == NULL || L2->Next->Data <= p->Next->Data) {
              // Insert L2 after p
              PtrToNode tmp = L2->Next;
              L2->Next = tmp->Next;
              tmp->Next = p->Next;
              p->Next = tmp;

              // Shift p
              p = p->Next;
          } else {
              p = p->Next;
          }
      }

      R->Next = L1->Next;
      L1->Next = NULL;

      return R;
  }

思路

对于一个 L1 中的活动节点,不断地将其与 L2 中的节点顺次比较,如果 L2 中的节点小于等于 L1 中的,那就将 L2 这个节点插入 L1 的活动节点的前面,并且 L2 变为 L2->Next。如果碰到 L1 的尾后节点(NULL 节点),将这个节点视作无穷大,一直插入 L2 中的节点;如果碰到 L2 的尾后节点,则循环结束。L1 即为所求。

但是题目的要求是 L1 最后也要变成 NULL,所以我们引入一个 R 节点,在结束的时候用它来代替 L1 的首前节点,而将 L1 这个节点本身的 Next 属性设置成为 NULL。