0.说在前面1.旋转链表2.相交链表3.作者的话
我们算法已经到了leetcode攀登之旅(21)!本周还差一次刷题推送,这篇就是,没错,让各位久等了,这次放的可是多种解法干货!!!
这次刷的题为旋转链表与相交链表!!! 说明一下,下面有个图文是我跟范大大组织的一次算法训练周计划!有想法的可以留言哈!
题目
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
思路
对于这个题目我想出了两种解法,现在分享一下。
解法一,让我想起了递归,然后未提交之前分析了一下复杂度,自己都觉得通过不了,你们懂的,递归效率不高!但是思路需要学会!
解法二,于是我开始想解法二,便发现了这道题的猫腻,那就是右移旋转k位置,如果是链表整数倍,那么旋转后链表不变,而如果不是链表整数倍,那么我们算出他的余数(k除以链表长度),真正移动的就是这个余数!
那么下面一起来实战吧!
实现
【递归实现】
这个算法,仅供研读学习思路,通不过的哈,超时。。。递归算法效率本身就不高!
class Solution(object):
def rotateRight(self, head, k):
if k == 0 or head is None or head.next is None:
return head
for i in range(k):
head = self.rightShift(head)
return head
def rightShift(self, head):
pre = head
curr = head.next
while curr:
if curr.next is None:
curr.next = head
pre.next = None
return curr
pre = pre.next
curr = curr.next
return curr
【获取真正k实现】
这个算法的关键在于,获取真正的右移次数,可以有效的解决时间复杂度问题!所以这里我将我的这个算法命名为获取真正k实现!
算法思路实现步骤:
k为0,链表为空或者只有一个结点旋转后,还是本身,所以直接返回!
(1)循环链表一次,获取链表长度!
pre代表右旋转后的链表的最后一个结点,curr代表右旋转的后面链表前置的头结点!
这里举个实际例子,如图所示:
class Solution(object):
def rotateRight(self, head, k):
if k==0 or head is None or head.next is None:
return head
p=head
size=0
while p:
size+=1
p=p.next
# 所循环的真实k
# 真实k为原始k除以链表长度取模
k=k%size
p=head
pre=head
curr=head.next
'''
(1)真实k如果不为0,参照算法图
(2)真实k如果为0,也就是原始k能够整除链表长度,
那么此时的节点旋转后还是原链表,直接返回原链表
'''
if k:
for i in range(size-k):
pre=p
curr=p.next
p=p.next
# 右旋转后的链表的最后一个结点next指向空
pre.next=None
# 保存最终链表的头节点
newhead=curr
# 循环后面移动到前面链表的所有结点,直到最后
while curr.next:
curr=curr.next
# 让上述尾部结点连接原先的头节点,构成一个完整链表
curr.next=head
return newhead
return head
算法分析
递归实现的时间复杂度为O(k*n),空间复杂度为O(n)
获取真实k实现的时间复杂度为O(n),空间复杂度为O(n)
题目
编写一个程序,找到两个单链表相交的起始节点。
例如,下面的两个链表:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
在节点 c1 开始相交。
注意:
null
.思路
对于这道题,也就是我今天想说的重点,这里给出哈希表,栈,以及双指针等多种解法!
算法思路直接写在代码实现处!
哈希表实现
直接定义一个字典,通过遍历链表A,并将A的所有结点添加到字典当中,循环遍历链表B,在字典中查找链表B的当前结点,如果存在,返回即可,否则为空!
def getIntersectionNode(self, headA, headB):
dictA={}
while headA:
dictA[headA]=0
headA=headA.next
while headB:
if headB in dictA:
return headB
headB=headB.next
return None
栈
这里定义两个list用来各自存放对应链表的结点,将链表A中结点入栈1,结点B中结点入栈2,我们知道只要两个链表相交,那么从相交点开始到后面的所有结点都一样!这里就通过弹出相同的结点,每次弹出的时候保存一下,直到找到两个链表的结点不同为止,此时返回刚才保存的结点,就是第一个相交的结点!
实现步骤:
首先特殊情况处理,然后结点各自入栈!首先需要判断一下最后结点相同不,如果不相同,直接不相交,返回None即可,否则需要对栈A与B出栈,并判断元素相同不!
def getIntersectionNode(self, headA, headB):
if headA is None or headB is None:
return None
stackA=[]
stackB=[]
while headA or headB:
if headA:
stackA.append(headA)
headA=headA.next
elif headB:
stackB.append(headB)
headB=headB.next
if stackA[-1]!=stackB[-1]:
return None
while stackA and stackB:
res=stackA[-1]
stackA.pop()
stackB.pop()
# 防止A与B栈空
if stackA and stackB:
if stackA[-1].val!=stackB[-1].val:
return res
else:
return res
return None
双指针计算size法
两个链表长度由于不一样,所以先通过循环找到各自链表的长度,然后让长链表的指针先走两个链表长度的差值,保证两个链表遍历长度一致!此时,让两个链表去比较,如果此时两个链表有相同结点,则相交,返回其中一个结点即可,否则返回None!
def getIntersectionNode(self, headA, headB):
if headA is None or headB is None:
return None
size_A = 0
size_B = 0
pA = headA
pB = headB
while pA or pB:
if pA:
size_A += 1
pA = pA.next
elif pB:
size_B += 1
pB = pB.next
if size_A > size_B:
inter = size_A - size_B
for i in range(inter):
headA = headA.next
elif size_A < size_B:
inter = size_B - size_A
for i in range(inter):
headB = headB.next
return self.search_Node(headA, headB)
def search_Node(self, headA, headB):
while headA:
if headA.val == headB.val:
return headA
headA = headA.next
headB = headB.next
return None
双指针不计算size法
对于这个实现,网上有个更牛逼的,直接几行代码写完,我们一起来拜读一下:
def getIntersectionNode(self, headA, headB):
p1 = headA
p2 = headB
while(p1 != p2):
p1 = headB if p1 == None else p1.next
p2 = headA if p2 == None else p2.next
return p1
双指针判断有无环状法
这里思路是将链表A先遍历到结尾,然后尾部连接头部,行成一个环,那么这道题就变成一个链表中是否有环问题。然后让链表B的头结点去访问即可!这里通过快慢指针来进行,对于这一块,之前写个证明,大家可以翻一下之前文章!
def getIntersectionNode(self, headA, headB):
if headA is None or headB is None:
return None
pA=headA
while pA.next:
pA=pA.next
pA.next=headA
return self.detectCycle(headB)
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
但是可惜这个方法通不过,他不允许修改链表结构,哈哈,天真了~~