#此题属于入门1题目
L1和L2是给定的带头结点的单链表， 其结点存储的数据是递增有序的； 函数Merge要将L1和L2合并为一个非递减的整数序列。 应直接使用原序列中的结点， 返回归并后的带头结点的链表头指针。
##Combine Link Listed
考察点
same 输入输出的例子两个完全一样的链表两个空链表L2完全贴在L1后面L1完全贴在L2后面让我们来翻译以上考擦点 1.例子中的输出和输入==比较节点的大小 小的先放入链表L 2. 两个从排序和大小完全相同的链表 3. 两个空链表 除了拥有头结点 4. L2链表任意节点都大于L1任意节点 5. L1链表任意节点大于L2任意节点
接下来我们逐步解决每一个问题
结构体数据
typedef int ElementType; typedef struct Node *PtrToNode; //struct Node struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List; List L; //这个就是返回的链表 p1 = L1->Next; //跳过头结点达到首元结点 p2 = L2->Next; // 同上 p3 = L; //p3 是链表L的指针 此时p3位于头结点 List tail //这个指针表示Node->Next //再例子中 L1 L2存在大小差异 所以问题的核心是 L1和L2 在L的大小差异 if(p1&&p2){ //解决问题3 两个空链表 for(;p1&&p2){ if(p1->Data < p2->Data){ tail = p1->Next; //把p1后一个节点存下来 p1->Next = NULL //断开原来节点的练习 p3->Next = p1; //链接链表L 成为L的一个节点 p3=p3->Next; //指向链表L的指针前进 p1 = tail; //p1指针前进 }else if(p1->Data > p2->Data){ tail = p2->Next; //把p2后一个节点存下来 p2->Next = NULL //断开原来节点的练习 p3->Next = p2; //链接链表L 成为L的一个节点 p3=p3->Next; //指向链表L的指针前进 p2 = tail; //p2指针前进 }else{ tail = p1->Next; //tail记载当前节点的下一个 p1->Next = NULL; //断开当前节点与后面的练习 p3->Next = p1; //链表L的指针指向p1 完成链接 p3 = p3->Next; //L的指针完成前进 p1 = tail; //p1又指回链表L1 tail = p2->Next; //同上 p2->Next = NULL; p3->Next = p2; p3 = p3->Next; p2 = tail; } } if(p1) { for(;p1;){ if(p3->Data <= p1->Data &&p3->Next==NULL){ tail = p1->Next; p3->Next = p1; p3 = p3->Next; p3->Next = NULL; p1 = tail; }else { printf("Fair"); } } } if(p2){ for(;p2;){ if(p3->Data <= p2->Data&&p3->Next==NULL){ tail = p2->Next; //记住L2节点的下一个,节点要被移到L上 p3->Next = p2; p3 = p3->Next; //P3指针前进移动至末尾 p3->Next = NULL; //将节点与原来链表L2的联系断开 p2 = tail; //将p2指针移动回原来节点的下一个 }else { printf("Fair!"); } } } p1 = L1; //指向头结点 p2 = L2; //指向头结点 p1->Next = NULL; //断开 p2->Next = NULL; } 此时if -else if()这一段代码块 思路是通过两个长短不同的链表进行合并 比较 总会留下一个L1或者L2的剩余链表 还有一个空链表 以及链表L 我们来判断 剩余的是L1还是L2 再然后用剩余的链表来跟链表L比较 接下来可以解决第二个问题 也就是 else() 也就是两个完全一样的链表 当节点既不是大于也不是小于 就可以分到等于 做法是 一次if完成两个节点的移动与前进 解决问题三 两个空链表 都是带头节点的空链表只要做判断 判断L1L2是不是空 如果为空就跳过if语句 问题4/5 问题所在可以用if语句来判断 最后最容易被忽视的一点 L1和L2的顺序为上的第一个节点 也就是头结点 头结点此时还是指向原来的首元结点 我们并未对头结点进行断开 所以还要在节点断开 使链表成为空链表上面都是解决问题的各小段 下面我出示完整代码
List Merge( List L1,List L2) /*合并两个有序链表成一个递增的有序列表*/ { List L = (List)malloc(sizeof(struct Node)); L->Next = NULL; List head = L; List p3 = head; //指向头结点 用来遍历链表L; List p1,p2,tail; p1 = L1->Next;//跳过头结点到达首元结点 p2 = L2->Next;//同上 if(p1&&p2){ /*存在L1,L2两个链表*/ for(;p1&&p2;){ if(p1->Data < p2->Data){ tail = p1->Next; //记录下一个 p1->Next = NULL; //把p1当前指向节点与后面节点断开 p3->Next = p1; //把L链表的当前节点指向需要添加的节点 完成连接 p3 = p3->Next; //链表L的指针向前移动 p1 = tail; //p1在指向L1链表原来节点的下一个 }else if(p1->Data > p2->Data){ tail = p2->Next; //重复使用 p2->Next = NULL; p3->Next = p2; p3 = p3->Next; p2 = tail; }else{ tail = p1->Next; p1->Next = NULL; p3->Next = p1; p3 = p3->Next; p1 = tail; tail = p2->Next; p2->Next = NULL; p3->Next = p2; p3 = p3->Next; p2 = tail; } } } if(p1) { for(;p1;){ if(p3->Data <= p1->Data &&p3->Next==NULL){ tail = p1->Next; p3->Next = p1; p3 = p3->Next; p3->Next = NULL; p1 = tail; }else { printf("Fair"); } } } if(p2){ for(;p2;){ if(p3->Data <= p2->Data&&p3->Next==NULL){ tail = p2->Next; //记住L2节点的下一个,节点要被移到L上 p3->Next = p2; p3 = p3->Next; //P3指针前进移动至末尾 p3->Next = NULL; //将节点与原来链表L2的联系断开 p2 = tail; //将p2指针移动回原来节点的下一个 }else { printf("Fair!"); } } } p1 = L1; p2 = L2; p1 ->Next = NULL; p2 ->Next = NULL; return L; }写的有些杂乱 语言来描述思路有点杂乱 下次争取用流程图来描述 如果有同学有不懂的问题 可以在评论区问我 我会及时回复你
属于只要懂链表知识 和足够的时间就能写出来 ↩︎
