快捷搜索:

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

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

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


合并两个有序链表

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

示例1:

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

示例2:

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

示例3:

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

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

思路

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

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

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

一些注意点:

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

代码

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
          
   
    struct ListNode* Head=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* 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;
    }

    struct ListNode* 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. 把两条链表断开。

代码

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

    cur=head;
    while(cur)
    {
          
   
        struct Node* copy=cur->next;
        if(cur->random==NULL)
        {
          
   
            copy->random=NULL;
        }
        else
        {
          
   
            copy->random=cur->random->next;
        }
        cur=cur->next->next;
    }
	struct Node* copytail=NULL;
	struct Node* copyhead=NULL;
    cur=head;
    while(cur)
    {
          
   
        struct Node* copy=cur->next;
        struct Node* 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),明显是不如上一种解法的,所以只是提供一个思路。 不细写。


最后

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

经验分享 程序员 职场和发展