[数据结构]题海啊，全是水（二） 合并两个有序链表，复制带随机指针的链表

总之这个是目录

菜鸡大学生的数据结构——刷题篇2
我想细心的读者已经发现了，今天只有两道题目，难道菜鸡大学生也要向时代妥协，转向研究快餐阅读了吗？
显然不是，只是菜鸡大学生最近白开水喝醉了，过几天就好了。

好了我编不下去了我们开始正题吧。

合并两个有序链表

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

示例1：

输入： l1 = [1,2,4], l2 = [1,3,4]
输出： [1,1,2,3,4,4]

示例2:

输入： l1 = [], l2 = []
输出： []

示例3:

输入： l1 = [], l2 = [0]
输出：[0]

这题不算难题，还是比较好解决的。

思路

构建一个新的链表，依次尾插链表较小的头节点。

既然是尾删我们就要考虑链表为空的状况，为了简化代码，我们这道题使用带哨兵位的头节点。

structListNode* Head=(structListNode*)malloc(sizeof(structListNode));structListNode* Tail=Head;
 Head->next=NULL;

一些注意点：

• 当其中一个链表结束的时候，我们只要把另一条链表直接接过去就行。
• 返回值为哨兵位的后一个节点。
• Head->next=NULL是为了防止示例2两个空链表的情况。
• 最后记得要释放哨兵位。

代码

structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){structListNode* Head=(structListNode*)malloc(sizeof(structListNode));structListNode* Tail=Head;
    Head->next=NULL;while(list1&&list2){if(list1->val<list2->val){
            Tail->next=list1;
            Tail=list1;
            list1=list1->next;}else{
            Tail->next=list2;
            Tail=list2;
            list2=list2->next;}}if(list1){
        Tail->next=list1;}if(list2){
        Tail->next=list2;}structListNode* ret=Head->next;free(Head);return ret;}

复制带随机指针的链表

题目嘎嘎长，菜鸡大学生的心嘎嘎凉。

那我们简单概括一下这道题目要我们干什么：把题目给的链表复制一遍。

这我熟啊，菜鸡大学生心想，我摸键盘这么多年，最擅长的就是ctrl+c和ctrl+v了。

那这道题何德何能排中等难度呢？我们看一下示例：

这题最麻烦的就是把random也拷贝下来。

但是，根据菜鸡大学生的研究，有一个十分精妙的解法，火速来与大家分享。

解法1

1. 在每一个节点后面插入一份相同的节点。
2. cur和copy指针遍历链表，copy的random就是cur的random的后一位。（如果random指向null就直接指向null）
3. 把两条链表断开。

代码

structNode*copyRandomList(structNode* head){structNode* cur=head;while(cur){structNode* copy=(structNode*)malloc(sizeof(structNode));
        copy->next=cur->next;
        copy->val=cur->val;
        cur->next=copy;
        cur=cur->next->next;}

    cur=head;while(cur){structNode* copy=cur->next;if(cur->random==NULL){
            copy->random=NULL;}else{
            copy->random=cur->random->next;}
        cur=cur->next->next;}structNode* copytail=NULL;structNode* copyhead=NULL;
    cur=head;while(cur){structNode* copy=cur->next;structNode* next=cur->next->next;

        cur->next=next;if(copyhead==NULL){
            copyhead=copytail=copy;}else{
            copytail->next=copy;
            copytail=copy;}
        cur=next;}return copyhead;}

解法2

暴力一点，先拷贝链表除random以外的节点，在原链表找出random指向节点的绝对位置，通过绝对位置在新链表里面确定random的指向。

这种方法的时间复杂度是O（N*N）,明显是不如上一种解法的，所以只是提供一个思路。
不细写。

最后

画图画图…好多要画的图画图画…画图…呜呜呜画图画图画图画图更多的画图画图…总之只有画图画图。