今天的题目都是单项链表,单向链表的特点是只能单向遍历。主要的优化角度在于减少内存使用。
24. 两两交换链表中的节点
用虚拟头结点,这样会方便很多。
本题链表操作就比较复杂了,建议大家先看视频,视频里我讲解了注意事项,为什么需要temp保存临时节点。题目链接/文章讲解/视频讲解。
这个题写了两种解法,dummy_head直接写,理清楚顺序;第二个方法是递归,while内部的动作其实是重复的即递归思想,这样可以省却了while以及init的处理。
这个题再次体现了C++语法的精准性,每一个指针指向的元素是什么都非常的清晰,非常有利于把抽象问题具体化,很适合加深理解数据结构。
Python方法一:dummy_head暴力遍历:
试了两种写交换元素的方法,如果同时写,那么同时交换,不用写tmp元素;如果逐行写,需要想清楚先后顺序,并且创建中间tmp元素。第二种较为简洁。
Python方法二:递归
也可以用递归来写,相对比较简洁。不用处理init和while的细节,且需要交换的元素较少。
C++方法一:dummy_head暴力遍历:
记得清除缓存变量。
c++ 不像 python,go 那种能这样交换两个变量的值。逗号运算符它会忽略掉左边的表达式。所以这里没有Python的简洁版写法。只能利用中间变量逐步替换。
C++方法二:递归
19.删除链表的倒数第N个节点
双指针的操作,要注意,删除第N个节点,那么我们当前遍历的指针一定要指向 第N个节点的前一个节点,建议先看视频。题目链接/文章讲解/视频讲解。
第一直觉是,遍历两遍,第一遍确定ListNode长度,第二遍删除第size-n个元素;遍历两遍提示我们可以用快慢指针来做,fast先走n步,再同时走slow fast直至最后一个node。细节上需要注意的是,考虑到n=1的情况,即删除最后一个元素,需要在倒数第二个元素时就决定,用dummy_head实现。
Python版本:
C++版本:
C++ 语法:
C++删除记得释放内存。
n--的用法是新学的。 C++:i++、++i、--i、i--、+=、-=、*=、/=你真的了解吗?
总是写错调用类属性的方式,head->next 而非head.next。
160. 链表相交
本题没有视频讲解,大家注意 数值相同,不代表指针相同。题目链接/文章讲解。
这个题和19题类似用到了快慢指针,思考逻辑是:如果倒过来遍历,那么最长的相同的node就是答案。而单链表只能单个方向遍历,于是需要先统计出两个链表的长度,求出长度差,之后的步骤就和19题类似了,快慢指针。
Leetcode在LinkList输出无效值的时候,输出None,不能空白或者输出int(0)。
Python版本:
C++版本:
142.环形链表II
算是链表比较有难度的题目,需要多花点时间理解 确定环和找环入口,建议先看视频。题目链接/文章讲解/视频讲解。
目前比较有意思的一个题,方法一是遍历,记录出现过的node,第二次出现的node即为入口,时间O(n), 但是内存[1+2+3+...+n ~ n^2]。那么就开始考虑是否可以优化内存到O(n),这个思路是经典的龟兔赛跑问题,用快慢指针的话一定会相遇,且图中x=z,在快指针只套了慢指针一圈的情况下,如果快指针比慢指针快了n圈(n>=2)的推导就比较妙了,x = (y+z)*k + z, 发现和n=1的情况是一样的,所以当快慢指针在met处相遇后,把慢指针放回head,那么下一次快慢指针相遇一定在x处。核心仍然是x=z。
Python方法一:暴力遍历
Python方法二:快慢指针
C++方法一:暴力遍历
C++关于集合的数据结构有set, unordered_set, map, unordered_map; unordered_set更接近Python中的set概念,但是这个题不能用unordered_set,因为集合内部元素是LinkList, unordered_set底层是hash_table, LinkList没有对应的hash函数,故不支持。所以适合map结构,map结构内部可以是LinkNode作为key。
C++方法二:快慢指针