数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下)

简介: 数据结构与算法⑥(第二章OJ题,下)后八道链表面试题

数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(中):https://developer.aliyun.com/article/1513365

11. 返回链表的深度拷贝

138. 复制带随机指针的链表

难度中等

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,

该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。

那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。

你的代码 接受原链表的头节点 head 作为传入参数。

示例 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]]

示例 3:

输入:head = [[3,null],[3,0],[3,null]]

输出:[[3,null],[3,0],[3,null]]

提示:

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.random 为 null 或指向链表中的节点。
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
struct Node* copyRandomList(struct Node* head) {
    
}

神奇代码:

很复杂的一题,要对链表增删查改很熟悉

可以用时间O(N^2)暴力法通过,会发现random非常的难处理

(因为原链表random的指向的节点在复制链表的对应的要指向的节点找不到了)

O(N^2)暴力法就是比较值是否相等,但是值有两个呢,这样又要麻烦了

以下是时间O(N)的很巧妙的方法:

2c0f61a80edf419ab50e337744fc6f0b.png

struct Node* copyRandomList(struct Node* head) {
    //1.插入复制节点到原节点的后面
    struct Node* cur = head;
    while (cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;//插入copy节点
        cur->next = copy;
 
        cur = copy->next;
    }
    //2.根据原节点处理复制节点的random
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    //3.复制节点解下来链接成一个新链表,恢复原链表链接关系
    struct Node* copy_head = NULL, * copy_tail = NULL;
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if (copy_head == NULL)//第一次进来
        {
            copy_head = copy_tail = copy;
        }
        else
        {
            copy_tail->next = copy;
            copy_tail = copy;
        }
        cur->next = next;
        cur = next;
    }
    return copy_head;
}

下面是后补的两道:

12. 对链表进行插入排序

(因为是穿越回来补的两道,所以对插入排序不懂的可以看看下面的链接:)

数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)_GR C的博客-CSDN博客

147. 对链表进行插入排序

难度中等

给定单个链表的头 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]

提示:

  • 列表中的节点数在 [1, 5000]范围内
  • -5000 <= Node.val <= 5000
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* insertionSortList(struct ListNode* head){
 
}

代码:

struct ListNode* insertionSortList(struct ListNode* head) {
    struct ListNode* new_head = malloc(sizeof(struct ListNode));
    new_head->val = 0;
    new_head->next = head;//新开一个节点指向头,最后返回这个节点的next
    struct ListNode* end = head;//设置end是已经插入好的链表的最后一个
    struct ListNode* cur = head->next;
    while (cur) 
    {
        if (end->val <= cur->val) //找比 已经插入好的最后一个 小的
        {
            end = end->next;
        }
        else 
        {
            struct ListNode* prev = new_head;
            while (prev->next->val <= cur->val) //找到了就再找cur应该插入的位置
            {
                prev = prev->next;
            }
            //插入
            end->next = cur->next;
            cur->next = prev->next;
            prev->next = cur;
        }
        cur = end->next;//cur=已经插入好的链表的最后一个的下一个,重复循环
    }
    struct ListNode* ret = new_head->next;
    free(new_head);
    return ret;
}

13. 删除链表中重复的结点

删除链表中重复的结点_牛客题霸_牛客网 (nowcoder.com)

JZ76 删除链表中重复的结点

中等 通过率:22.17% 时间限制:1秒 空间限制:64M

描述

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表 1->2->3->3->4->4->5 处理后为 1->2->5

数据范围:链表长度满足 0≤n≤1000 ,链表中的值满足 1≤val≤1000


进阶:空间复杂度 O(n) ,时间复杂度 O(n)


例如输入{1,2,3,3,4,4,5}时,对应的输出为{1,2,5},对应的输入输出链表如下图所示:

示例1

输入:

{1,2,3,3,4,4,5}

复制

返回值:

{1,2,5}

复制

示例2

输入:

{1,1,1,8}

复制

返回值:

{8}

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* deleteDuplication(struct ListNode* pHead ) {
    
}

代码:

struct ListNode* deleteDuplication(struct ListNode* pHead ) {
    if(pHead == NULL)
    {
        return NULL;
    }
    struct ListNode* new_head = malloc(sizeof(struct ListNode));
    new_head->val = 0;
    new_head->next = pHead;//新开一个节点指向头,最后返回这个节点的next
    struct ListNode* cur = new_head;
    while(cur->next && cur->next->next)
    {
        if(cur->next->val == cur->next->next->val)
        {
            int tmp = cur->next->val;//遇到两个节点相同的,记录下来并跳过
            while(cur->next && tmp == cur->next->val)
            {
                cur->next = cur->next->next;
            }
        }
        else
        {
            cur = cur->next;
        }
    }
    return new_head->next;
}

严谨代码:

ListNode* deleteDuplication(ListNode* pHead)
{
    if (pHead == NULL || pHead->next == NULL)
        return pHead;
 
    struct ListNode* n0 = NULL;
    struct ListNode* n1 = pHead;
    struct ListNode* n2 = n1->next;
    while (n2 != NULL)
    {
        //如果相邻节点不相同,则不需要删除,更新节点,继续向后遍历
        if (n1->val != n2->val)
        {
            n0 = n1;
            n1 = n2;
            n2 = n2->next;
        }
        else
        {
            //如果相邻节点相同
            //则n2去找第一个不相同的节点
            while (n2 && n2->val == n1->val)
            {
                n2 = n2->next;
            }
            //重新链接,如果要删除的包括头节点,则更新头节点
            if (n0)
                n0->next = n2;
            else
                pHead = n2;
 
            // 删除掉重复的节点
            while (n1 != n2)
            {
                struct ListNode* next = n1->next;
                free(n1);
                n1 = next;
            }
            //更新节点
            n1 = n2;
            if (n2)
                n2 = n2->next;
        }
    }
    return pHead;
}

链表其它题链接:

力扣:https://leetcode.cn/tag/linked-list/problemset/

牛客https://www.nowcoder.com/exam/oj

本篇完。

9b549b5323ee45b983d1b741dd5b13b1.jpg

目录
相关文章
|
3天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
7天前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
11 0
|
7天前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
17 0
|
7天前
|
存储 算法
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
8 0
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
|
7天前
|
算法
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
8 0
|
7天前
|
算法
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
8 0
|
7天前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
7 0
|
9天前
|
存储 缓存 算法
【数据结构】栈和队列的模拟实现(两个方式实现)
【数据结构】栈和队列的模拟实现(两个方式实现)
|
2天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
10 3
|
2天前
数据结构初阶 栈
数据结构初阶 栈
7 1