【数据结构与算法】链表之美-复杂链表的复制与链表的插入排序

发布于:2024-11-29 ⋅ 阅读:(27) ⋅ 点赞:(0)

主页:HABUO🍁主页:HABUO

🍁如果再也不能见到你,祝你早安,午安,晚安🍁


1.复杂链表的复制

题目:请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null

示例1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2:

输入:head = [[1,1],[2,1]]

输出:[[1,1],[2,1]]

分析:这是一个比较复杂的题目,我们只有见的多了之后我们可能看到这样新的题目,才会有敲门砖,又时候差的就是刚开始的敲门砖,敲门砖有了,剩下的就是用我们之前拥有的思想去实现就完了。因此呢,在这里我直接给出这个思路,以后再遇到这样类型的我们是不是就会了啊。首先,我们直接遍历是不是没办法搞啊,因为你random不知道指向谁,有些人可能会说,那我直接访问该节点的random不就行了,是的,但是如果我们链表当中,有两个相同值的节点怎么办?因为我们复制节点是复制它们的值和指向,地址是不是同等的复制下来,假如两个3,你只知道random指向3的那个节点,但是具体哪个节点我们是不是无能为力啊。因此这种直接的方法难以实现。好了,接下来很重要,1.我们为每一个节点备份一个节点,而且呢,让这个节点的next指向这个备份节点,让备份节点的next指向原链表该节点的next。2.让每一个备份节点的random指向它应该指向的备份节点,有人会问,那这咋指向,好关键点来了,你发现没有,备份节点的random是不是就是原节点的random的next啊,对不对,这就是这个题的关键。3.恢复原链表,让新链表链接起来,并返回头指针。这就是我们整体的思路。下面进行一步一步实现。

第一步:为每个节点进行备份,并且让这个节点的next指向这个备份节点,让备份节点的next指向原链表该节点的next,由于random画上之后错综复杂,不再指出,本题以示例1为导向。如下图所示:

代码实现如下:

//1.为每个链表节点备份一个节点
    Node* cur = head;
    while(cur)
    {
        Node* copyNode = (Node*)malloc(sizeof(Node));
        copyNode->val = cur->val;
        copyNode->next = cur->next;
        cur->next = copyNode;
        cur = copyNode->next;
    }

第二步 让每一个备份节点的random指向它应该指向的备份节点,我们以13节点为例,看下图就会明白。因为每一个节点的备份节点是不是就是原节点的next因此我们想要备份节点指向它所指向的random,找到原节点的random是不是就行了啊。

代码实现如下:

//2.为备份节点的random进行链接
    cur = head;
    while(cur)
    {
        //cur->random有可能指向NULL
        if(cur->random == NULL)
        {
            cur->next->random = NULL;
            cur = cur->next->next;
            continue;
        }
        //每个备份节点的random,都是原节点的random的备份节点
        cur->next->random = cur->random->next;
        cur = cur->next->next;
    }

第三步,我们破坏了原链表的链接是不是需要恢复,而且新链表也还没有连接上,下面是不是就是恢复和链接,这里就只需要多设置几个指针来回的走就ok,前面的几道题的铺垫,相信这对于我们来说应该相对很简单。

//恢复原链表,把备份链表进行链接
    cur = head;
    Node* newHead = cur->next;
    Node* copyCur = newHead;
    Node* curNext = newHead->next;
    while(cur)
    {
        cur->next = curNext;
        if(curNext == NULL)
        {
            copyCur->next = NULL;
            break;
        }
        copyCur->next = curNext->next;
        copyCur = copyCur->next;
        cur = curNext;
        curNext = curNext->next->next;
    }
    return newHead;

要注意curNext是不是到最后就为NULL了,但是我们下面还有要访问它的next的代码,因此需要在这之前做一个判断语句做一个判断,防止错误。需要注意我们这种方法是不是对原链表进行修改了,这种操作是不太好的,等到好面我们学习的深入会用更优的方法去解决。

2.对链表进行插入排序

题目:给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。

插入排序 算法的步骤:

  1. 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
  2. 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
  3. 重复直到所有输入数据插入完为止。

示例1:

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

示例2:

输入: head = [-1,5,3,4,0]              输出: [-1,0,3,4,5]

分析:我们可能直接的想法就是从第一个数据起,拿到一个数据就从头遍历放到合适的位置直至最后一个节点。 但是这是链表啊,这样操作是不是代价也太高了,要是数组你发到一个合适的位置,只需要将后面的数据往后移动即可,链表不太行。所以,我们的思路是,将第一个节点当作一个新链表的起始节点,之后从后面链表当中每次取一个节点,往新链表当中进行逐一比较进行插入,当然有可能头插,也有可能尾插,也可能中间插入,所以分三种情况,这就是我们的大致思想,具体如下图所示:

所以分三种情况进行插入,头插实现如下:注意我们一开始让head指向了head->next,因为我们让第一个节点当作新链表的头了

//头插
        if(cur->val >= head->val)
        {
            head->next = cur;
            cur = head;
            newHead = cur;
            head =headNext;
            if(headNext == NULL)
                break;
            headNext = headNext->next;
            continue;
        }

中间插入实现代码如下:

while(cur)
        {
            //中间插入
            if(cur->val < head->val)
            {
                curPrev = cur;
                cur = cur->next;
            }
            else
            {
                head->next = cur;
                curPrev->next = head;
                head = headNext;
                if(headNext == NULL)
                    break;
                headNext = headNext->next;
                break;
            }
        }

尾插的话是不是就是中间插入情况的cur指向了NULL还没找到合适的位置,因此实现代码如下:

//尾插
        if(cur == NULL)
        {
            curPrev->next = head;
            head->next = NULL;
            head = headNext;
            if(headNext == NULL)
                break;
            headNext = headNext->next;
        }

所以将这些代码串起来放到一个循环当中是不是就实现了,因此完整代码如下:

 typedef struct ListNode Node;
struct ListNode* insertionSortList(struct ListNode* head) {
    if(head == NULL || head->next == NULL)
        return head;
    Node* newHead = head;
    head = head->next;
    newHead->next = NULL;
    Node* headNext = head->next;
    while(head) 
    {
        Node* cur = newHead;
        Node* curPrev = NULL;
        //头插
        if(cur->val >= head->val)
        {
            head->next = cur;
            cur = head;
            newHead = cur;
            head =headNext;
            if(headNext == NULL)
                break;
            headNext = headNext->next;
            continue;
        }
        while(cur)
        {
            //中间插入
            if(cur->val < head->val)
            {
                curPrev = cur;
                cur = cur->next;
            }
            else
            {
                head->next = cur;
                curPrev->next = head;
                head = headNext;
                if(headNext == NULL)
                    break;
                headNext = headNext->next;
                break;
            }
        }
        //尾插
        if(cur == NULL)
        {
            curPrev->next = head;
            head->next = NULL;
            head = headNext;
            if(headNext == NULL)
                break;
            headNext = headNext->next;
        }
    }
    return newHead;
}

 总结:本篇博客介绍了两个有关链表的两个题,相对于前面我们所介绍的题,可能有些难度,但这些难度是不是都是在思路上,如果有了这个思路实现起来是不是还是用我们前面的思想啊,因此我们别畏惧它,相信通过夜以继日的敲代码,我们肯定会拿到一个难题就会有思路的。大家加油!💯


🌻数据结构与算法专栏🌻

🤜别放弃是我们的底色,加油!🤛

🏋不是每一粒种子都能开花,但播下种子就比荒芜的旷野强百倍🏋