首页
学习
活动
专区
圈层
工具
发布

【初阶数据结构】——链表常见面试题剖析

我们从头去遍历链表,如果链表结点的值等于val,我们就把当前结点删除并释放掉,如果结点的值不等于val,我就把它尾插到一个新的空链表上。...因为我们只是把原链表的结点拿了下来进行尾插,并没有创建新的结点。...我们来画一下图: 那大家再来思考一下,这些操作我们肯定要放在循环中进行,那循环结束的条件应该是什么? ,是不是只要有其中一个链表遍历结束,整个循环就应该结束了。 循环结束就完了吗?...tail->next=list2; tail=list2; list2=list2->next; } } if(list1...那我们在操作时是不是也得需要两个指针,来保存相邻两个结点的地址啊。 两个指针够不够?

25210
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    【41期】盘点那些必问的数据结构算法题之链表

    双向链表在redis中有很好的实现,也在我的仓库中拷贝了一份用于测试用,本文的相关代码在 这里。...当然我们可以遍历list1时,使用哈希表存储list1的结点,这样再遍历list2即可判断了,时间复杂度为O(length(list1) + length(list2)),空间复杂度为 O(length...如果存在环,假定快慢指针经过s次循环后相遇,则此时快指针走的距离为 2s,慢指针走的距离为 s,假定环内结点数为r,则要相遇则必须满足下面条件,即相遇时次数满足 s = nr。...前面已经可知道第一次相遇要循环 r 次,而相遇时慢指针走的距离为 s=r,设链表总长度为L,链表头到环入口的距离为a,环入口到相遇点的距离为x,则L = a + r,可以推导出 a = (L-x-a),...其中L-x-a为相遇点到环入口点的距离,即链表头到环入口的距离a等于相遇点到环入口距离。

    62830

    链表面试题

    然后使用 while 循环遍历链表,当快指针 fast 到达链表的末尾或者为空时,遍历结束。在循环过程中,每次快指针移动两步,慢指针移动一步。最终返回慢指针 slow,即为链表的中间节点。...使用while循环遍历list1和list2,比较当前节点的值大小,将较小的节点添加到新链表中。 当一个链表遍历完后,将另一个链表中剩余的节点全部添加到新链表的尾部。...list2; if(list2==NULL) return list1; struct ListNode* tail = NULL,*head = NULL; while(list1 && list2...tail->next = list2; tail = tail->next; } list2 = list2->next; } } if(list1) tail->next = list1; if(list2...❣️2.解答 在原链表中每个节点的后面插入一个新的节点,新节点的值等于原节点的值,新节点的 next 指针等于原节点的 next 指针。

    15610

    如何使用 Python 检查两个列表是否反向相等?

    在 Python 中使用列表时,在某些情况下,您可能需要比较两个列表是否反向相等。这意味着一个列表中的元素与另一个列表中的元素相同,但顺序相反。...如果反向列表等于原始列表,我们可以说两个列表是反向相等的。...语法 reversed_list1 = list1[::-1] 在这里,使用切片语法 list1[::-1] 创建 list1 的反向版本,该语法返回一个包含相反顺序元素的新列表。...该函数反转 list1 并检查它是否等于 list2。由于反转列表等于 list2,因此输出为 True。..., 3, 2, 1] print(are_lists_reverse_equal(list1, list2)) 输出 True 结论 在本文中,我们讨论了如何在 Python 中使用不同的方式检查两个列表是否反向相等

    1.3K20

    盘点那些必问的数据结构算法题之链表

    双向链表在redis中有很好的实现,也在我的仓库中拷贝了一份用于测试用,本文的相关代码在 这里。...当然我们可以遍历list1时,使用哈希表存储list1的结点,这样再遍历list2即可判断了,时间复杂度为O(length(list1) + length(list2)),空间复杂度为 O(length...如果存在环,假定快慢指针经过s次循环后相遇,则此时快指针走的距离为 2s,慢指针走的距离为 s,假定环内结点数为r,则要相遇则必须满足下面条件,即相遇时次数满足 s = nr。...前面已经可知道第一次相遇要循环 r 次,而相遇时慢指针走的距离为 s=r,设链表总长度为L,链表头到环入口的距离为a,环入口到相遇点的距离为x,则L = a + r,可以推导出 a = (L-x-a),...其中L-x-a为相遇点到环入口点的距离,即链表头到环入口的距离a等于相遇点到环入口距离。

    14210

    【Leetcode -21.合并两个有序链表 -83.删除排序链表中的重复元素】

    ,先定义两个结构体的空指针head和tail,然后先第一次比较list1和list2,谁小就把它的头节点赋给head和tail,然后更新list1或者list2;如图: 然后进入循环进行比较,当list1...和list2都为非空,就进入循环,比较list1和list2谁小,假如list1小就把它放到tail的next,然后更新tail,更新list1;list2也同理;直到其中有一个空,就把另外一个非空的直接链接上...//当list1和list2都不为空,循环继续 while (list1 && list2) { //开始逐一比较,假如list1小就把它放到...//list2小或者等于就把它放到tail的next,然后更新tail,更新list2 else { tail->next = list2...等于del的val,即出现了重复元素 if (cur->val == del->val) { //将del的next赋给cur的next

    22510

    【数据结构与算法】合并链表、链表分割、链表回文结构

    return list1; 又我们的循环条件为:list1 && list2,因此最后是不list1或者list2必须有一个为NULL,但是另一个肯定还没走到最后,因此需要继续: if (list1)...{ Tail->next = list1; Tail = list1; } if (list2) { Tail->next = list2; Tail = list2;...保证链表长度小于等于900。 测试样例:1->2->2->1 返回:true 分析:一般这种链表题它给的都是单链表,你说它坑不坑,就是让你难受,但是我劝你别烦,听我娓娓道来。...补充: Node* Head = NULL, * Tail = NULL;使用这种方式定义时一定要注意前面的变量也需要初始化,它不是跟后面一起的,两个都需要独立的进行操作,在做这几道题的时候,我用了这种定义的方式可把我害惨了‍...总结:本篇博客介绍了三道题,这三道题不约而同的用到了我们前面所学到的知识,我相信通过这几道题的应用,我们对前面的知识,无论时反转链表、找中间节点等题型都了然于胸,我们也接触到了一个新题型判断链表的回文结构

    15400

    【数据结构】----单链表相关题目【小白必看!!!】

    ListNode* list2) { if(list1==NULL) { return list2; } if(list2==NULL) {...用来往下进行,下面用while循环遍历,然后遍历结束之后,我们还要检查一下此时的list1和list2是否是为空,不是空就要将他们剩余的节点加在我们的链表之后。...,就是给你一个链表,然后给你一个val,将这个链表的等于这个val的节点全部移除,输出剩下的节点,这个题我们的思路也是创建一个新的链表,然后我们去遍历原链表,等于这个值就跳过,否则添加到新链表当中。...head = [1,2,6,3,4,5,6], val = 6,那么while循环之后最后一位是不是很就是6了,而不是空指针,因为最后一个节点是val,所以while循环时不会进入if语句,所以此时newTail...最后for循环结束之后,再令最后一个点指向第一个节点,这样就实现了一个环形链表,然后我们开始进行while循环,因为我们要求是求出最后一个节点,所以剩下最后一个节点时它会指向自己,所以我们while循环的条件就是

    15710

    剑指Offer-合并两个排序的链表

    思路 思路一(迭代): 首先处理空链表,当其中一个为空链表时,直接输出另一个;当两个均为空链表时,输出null。 初始化两个链表头,其中一个表头用以记录两个链表比较后的结果,另一个用来返回结果。...循环,如果两个链表不为空,进行比较,并将值小的赋给合并的链表头cur,值小的链表向后移动一位,合并链表cur向后移动一位。 如果两个链表有一为空,循环结束,把未结束的链表直接连接到合并链表的尾部。...思路二(递归): 首先处理空链表,当其中一个为空链表时,直接输出另一个;当两个均为空链表时,输出null。...比较 list1 和 list2 的头结点,较小的头结点作为合并后新链表的头结点 确定新链表的头结点之后,就可以递归比较余下的结点了 代码实现 package LinkedList; /** * 合并两个排序的链表...) {//如果链表1的结点小于等于链表2的结点 list1.next = Merge(list1.next, list2); return list1;

    60140

    Python学习的自我理解和想法(9)

    1.赋值 语法:变量 = 值 自我理解:其实就是对那个值起别名来引用. 2.浅拷贝,深拷贝存在原因 自我理解:如果我们定义一个list1=[a,b,c,d,e],list2=list1,那么修改list1...时也会改变我们list2的值,为了解决这个问题,出现了深拷贝和浅拷贝这个说法. 3.底层逻辑 当我们直接写list2=list1时,list1和list2同时指向一个储存地址,所以一变万变. 4.浅拷贝...语法:[导入copy模块] list.copy 自我理解:copy函数相当于将list1和list2的储存地址分开,所以可以独立改变....在上面的例子中,列表3中的第三个元素是一个可变的列表。当我们创建了浅拷贝list4后,4中的第三个元素仍然是指向内存中那个的引用。...当我们创建了深拷贝6 后,6中的每一个元素,包括那个嵌套的列表,都是全新创建的,与原始对象5中的对应元素没有任何引用关系。

    11000

    2-2 线性表之链表 及其C++实现

    ,并且可以方便地随机存取表中的任一元素,但是从它的插入和删除算法可以看出,顺序表的效率较低,需要大量的数据元素的移位。...; return NAN; } return p->data; } 这个函数描述了,我如何在链表中找到第i个位置的元素,这个函数只要熟悉了,其实链表的插入 和 删除...= i - 1) {//如果跳出循环是j并不是i-1,说明停止时发生的条件是 p->next==nullptr; cout list1) << endl; Show(list1); /*也可以用我写的那个Create程序创建新链表,但是要注意一点: 我那个程序是针对没有被初始化过的链表指针,因为那个函数里面有初始化语句...(list1) << endl; Show(list1); /*也可以用我写的那个Create程序创建新链表,但是要注意一点: 我那个程序是针对没有被初始化过的链表指针,因为那个函数里面有初始化语句

    1.3K20

    Java真的有引用传递吗?

    > list1 = new ArrayList(); list1.add("1"); List list2= new ArrayList();...首先我个人猜测了一下错误的原因:大家可能是被值传递和引用传递这个概念误导了,我们在经历过的面试的中,应该都会被问到值传递和引用传递的区别,通常我们会会值传递的是数据的拷贝,对拷贝值的操作不会影响到原值,...其实不然,引用传递,我们传递的是引用类型变量的拷贝(值传递),但是拷贝变量指向堆中的地址和原址是一样的,当我们操作拷贝变量而不是拷贝变量指向的地址时,是不会影响原值的。...如果上面的描述你还是不懂,我们来具体解析一下上面的面试题: 首先我们调用 swap(list1,list2) 时候,会将list1和list2拷贝一份,然后传递到swap方法中,而swap方法中,将e和...e1进行交换,实际上并不是对list1和list2的操作,自然不会影响到list1和list2的值。

    3K40
    领券