Leetcode 链表 算法练习
算法与数据结构学习仓库地址:https://spiritling.coding.net/public/public/AaDS-docs-code/git/files
下面短网址失效的可以使用这个原始地址
237 删除链表中的节点
地址:https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
题目
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。
解题思路
首先这个题目刚开始有点影响人的判断。
我以为函数中传入的是整个链表结构。(⊙﹏⊙)
然后就错了。。。
再次看题时,发现传入的是删除的节点,那么就简单了一部分
首先,要删除这个节点,常规来说就是通过改变上一节点的指向来删除节点。
但是很不幸的是,这个节点结构中是不存在 prev
指向,那么也就无法通过改变上一节点来删除。
既然这个节点存在,有值,有指向。
那么我们可不可以将这个节点的值改为下个节点的值,相应的这个节点的值就被删除了,其实是覆盖了。
改变了值,那么同样的需要改变 next
的指向,将其指向到下一个节点的下一个。
实际就是将下个节点复制到删除的节点这里,覆盖掉需要删除的节点。
代码
1 | /** |
1290. 二进制链表转整数
地址:https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer/
题目
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
解题思路
第一版:
链表不是 1 就是 0,所以我想的是,直接将所有值拼接成字符串。
然后通过 c#自带的进制转换,将其二进制字符串转为十进制。
但是相应的,这个也有缺点,感觉没有对最前面为 0 的额外处理。
第二版:
利用进制转换算法,可以直接将二进制转为十进制,而不需要去调用其他方法。
并且直接使用传入进来的参数来进行赋值和操作。
代码
第一版:
时间复杂度分析:O(n)
1 | /** |
第二版:
1 | /** |
206. 反转链表
地址:https://leetcode-cn.com/problems/reverse-linked-list/
题目
反转一个单链表
1 | 输入: 1->2->3->4->5->NULL |
解题思路
第一版:首先反应想到的
时间复杂度:O(n^2)
看到题目第一时间想到的方式,首先将每个值拿出来,然后再将存放的数组反转下,在构建新的链表。
方式比较差劲,后续改进了下
第二版:递归方式
题目描述中,说可以使用迭代和递归方式进行。
创建个函数,处理每一个节点,将每个节点赋值新的节点,然后将传递进来的节点赋值到新的节点的 next 上,并且传递下个递归,层层下去
当按顺序传递进去的节点的 next 为 null 时,返回最后节点。
第三版:迭代方式
这个方式跑了两遍,第一遍 120 毫秒左右,第二遍跑了 104 毫秒 O(∩_∩)O 😄 。
迭代是一种不断用变量的旧值递推出新值的解决问题的方法。
所以在 while 循环链表时,将当前旧值赋值给新的节点,并且将新的节点 next 指向 prev
最后在反向赋值下,将临时的赋值给 prev
将 head 赋值为 head.next,继续循环,直到为 null
代码
第一版:首先想到的,比较差
1 | public ListNode ReverseList(ListNode head) |
第二版:递归方式
1 | public ListNode ReverseList2(ListNode head) |
第三版:迭代方式
1 | public ListNode ReverseList3(ListNode head) |
O(∩_∩)O 😄 这个方式跑了两遍,第一遍 120 毫秒左右,第二遍跑了 104 毫秒。
876. 链表的中间结点
地址:https://leetcode-cn.com/problems/middle-of-the-linked-list/
解题思路
找出中间值,一旦涉及到中间的处理,在链表中都可以使用快慢指针的方式
快指针每次两步
慢指针每次一步
当快指针为 null 或者它的下一个是 null
则证明到了末尾,然后同时返回慢指针的值(这个题好处就是如果是两个中间返回后一个),就是剩余的后半部分
具体末尾图看图
代码
1 | /** |
手画图

