LeetCode之链表(10)
- 2019 年 10 月 5 日
- 笔记
LeetCode之链表(10)
0.说在前面
1.反转链表
2.两两交换节点
3.环形链表
4.环形链表II
5.作者的话
0.说在前面
今天有点闲，就来连刷几道题，下次不这样干了，有点hold不住，建议以后保持平衡刷题规律！
今天的刷题主要来介绍链表的基本操作。采用语言为python。
在py中，链表值访问与next指针访问有点稍微不同。
p.val p.next
没错，就这么简单，py就是这么随意，简单明了访问！
下面列出今天刷的题的名字：
- 反转链表
- 两两交换链表中的节点
- 环形链表
- 环形链表II
四道题。。。是不是有点崩溃~~其实只有两道，第一道很easy的一道，后面两个环形链表与环形链表II合并为一个，总共就只有两个，不多吧，哈哈~开始刷题！
1.反转链表
【问题】
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
【思路】
直接把None定义为前节点，这个可是非常有用！
然后定义一个当前节点，通过当前节点与前一节点的连接进行反转！
【实现】
下面给出大佬的解法~~几行精简代码，自己写的有点不好看，就不给出来了！
class Solution: def reverseList(self, head): cur,prev=head,None while cur: cur.next,prev,cur=prev,cur,cur.next return prev
【复杂度】
时间复杂度：O(n)，空间复杂度：O(1)
2.两两交换节点
【问题】
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
说明:
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
【思路】
特殊情况：当链表为空或者只有一个节点时候，直接返回当前链表；
一般情况，看下图：
图中给出了算法的思想，现在来文字描述一下：
首先定义一个链表构成为a->b->c->d->e->f
第一步，定义两个指针p，q，当分别指向head与head.next节点，当a与b交换的情况下则是如图所示b连a的线；
第二步：我们要做的就是断开a与b的原先连线与bc之间的连线，并定义一个指针指向节点c，用于保存后面的节点；
第三步：我们知道下一个是c与d反转，那么a肯定是跟d连接，也就是a指向了temp.next节点；
第四步：让p指向temp所指的节点c，q指向d节点，那么后面你会发现只需要重复上述操作即可。
这里有个注意点：当链表节点为奇数与偶数情况，如上是偶数节点，当为奇数节点的时候，假设现在有3个节点a->b->c所构成的链表，那么反转后为b->a->c，此时你会注意到，当使用上述图的方法的时候，只有temp没有temp.next，那么这一块怎么处理呢?
呀，看到分情况了，是不是想到了If判断！
对头，只需要If判断，当temp为空，也就偶数节点，此时最终结束就是直接让前一个p节点直接指向None即可，当temp.next为空，此时为奇数个节点，此时就是直接让前一个p节点直接指向当前的temp节点即可！
思路讲解完毕，开始实现环节！
【实现】
class Solution: def swapPairs(self, head): p=head if p==None or p.next==None: return p # 根据上面的图来看这里 new_node = p.next while(1): q=p.next temp=q.next q.next=p if (temp==None): p.next=None break if (temp.next==None): p.next=temp break p.next=temp.next p=temp return new_node
【复杂度】
时间复杂度：O(n)，空间复杂度：O(1)
3.环形链表
【问题】
给定一个链表，判断链表中是否有环。
【思路1】
使用hashset方法，使用hash的去重思想，只要跟集合当中的元素重复，就可以发现，此时说明有环；若没有发现，则无环！
注意：这个问题只是在最后有一个环，看后面的图！
【实现1】
class Solution(object): def hasCycle(self, head): hash_set=set() while head: if head in hash_set: return True else: hash_set.add(head) head=head.next return False
【复杂度1】
时间复杂度：O(n)，空间复杂度：O(n)
【思路2】
这个参考了网上的思路，这个思想听说有点反人类。。
就是龟兔赛跑方法，定义一个快指针，一个慢指针，当相遇，则有环，否则无环。
【实现2】
个人版
class Solution(object): def hasCycle(self, head): if head==None or head.next==None: return False slow=head fast=head.next while slow!=fast: if fast==None or fast.next==None: return False slow=slow.next fast=fast.next.next return True
升级版
class Solution(object): def hasCycle(self, head): slow=fast=head while slow and fast and fast.next: slow=slow.next fast=fast.next.next if slow==fast: return True return False
【复杂度2】
时间复杂度：O(n)，空间复杂度：O(1)
4.环形链表II
【问题】
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
【思路】
这道题实际上是上述题的扩展，这里我优先想到了上述的hashset方法，我们知道只需要当碰到重复元素的时候，直接相当于定位到了环的起始位节点，也就是直接返回链表开始入环的第一个节点。如果链表无环，则返回 null。注意用python写，得改成None!
【实现1】
class Solution(object): def detectCycle(self, head): """ :type head: ListNode :rtype: ListNode """ hash_set=set() while head: if head in hash_set: return head else: hash_set.add(head) head=head.next return None
【复杂度1】
时间复杂度：O(n)，空间复杂度：O(n)
【思路2】
这个当时没想出来，当时想着应该可以用上述的解法二去破解这个拓展问题，结果发现确实可以，就是得在数学上证明一下。。。这个套路太深。。
下面我们来看一下数学证明：
如上图所示：直线表示链表，圆圈表示环，分别有X(链表起始点)，Y(环起始点)，Z(快慢指针第一次相遇点)，a为XY距离，b为Y距离，c为YZ距离。
我们知道当快指针速度为2，满指针速度为1，快慢指针相遇的时候，此时慢指针走过的距离为a+b，而快指针走过的距离为a+2b+c。
根据速度知道：2(a+b)=a+2b+c，立即推：a=c。
那么关键点来了，a=c有啥子用呢？
首先来陈述一下a=c的意思，当快慢指针相遇于Z点，此时链表开始位置距离Y与相遇点距离Y相等。
这下算法思路来了，还是按照上述的解法二，龟兔赛跑找出相遇点Z，然后给个循环，让慢的指针与head指针不断比较，知道两个指针指向相同，那么此时就都抵达Y点了，也就是找到了我们想要的第一次进入环的节点！
是不是很神奇~~
【实现2】
那么我们在上面代码里面加个小循环即可实现！
class Solution(object): def detectCycle(self, head): if not head: return None slow = fast = head while(slow and fast): slow, fast =slow.next, fast.next if fast: fast = fast.next if slow is fast: while(slow is not head): slow, head = slow.next, head.next return head return None
【复杂度2】
时间复杂度：O(n)，空间复杂度：O(1)
5.作者的话
最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！
更多内容，请关注本公众号算法系列！
