0.说在前面
1.反转链表
2.两两交换节点
3.环形链表
4.环形链表II
5.作者的话
今天有点闲,就来连刷几道题,下次不这样干了,有点hold不住,建议以后保持平衡刷题规律!
今天的刷题主要来介绍链表的基本操作。采用语言为python。
在py中,链表值访问与next指针访问有点稍微不同。
p.val
p.next
没错,就这么简单,py就是这么随意,简单明了访问!
下面列出今天刷的题的名字:
四道题。。。是不是有点崩溃~~其实只有两道,第一道很easy的一道,后面两个环形链表与环形链表II合并为一个,总共就只有两个,不多吧,哈哈~开始刷题!
【问题】
反转一个单链表。
示例:
输入: 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)
【问题】
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
示例:
给定 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)
【问题】
给定一个链表,判断链表中是否有环。
【思路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)
【问题】
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 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)
最后,您如果觉得本公众号对您有帮助,欢迎您多多支持,转发,谢谢!
更多内容,请关注本公众号算法系列!