多种解法破解链表
多种解法破解链表
多种解法破解链表
0.说在前面1.旋转链表2.相交链表3.作者的话
0.说在前面
我们算法已经到了leetcode攀登之旅(21)!本周还差一次刷题推送，这篇就是，没错，让各位久等了，这次放的可是多种解法干货！！！
这次刷的题为旋转链表与相交链表！！！ 说明一下，下面有个图文是我跟范大大组织的一次算法训练周计划！有想法的可以留言哈！
1.旋转链表
题目
给定一个链表，旋转链表，将链表每个节点向右移动 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)
2.相交链表
题目
编写一个程序，找到两个单链表相交的起始节点。
例如，下面的两个链表：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
在节点 c1 开始相交。
注意：
- 如果两个链表没有交点，返回
null. - 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
思路
对于这道题，也就是我今天想说的重点，这里给出哈希表，栈，以及双指针等多种解法！
算法思路直接写在代码实现处！
哈希表实现
直接定义一个字典，通过遍历链表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
但是可惜这个方法通不过，他不允许修改链表结构，哈哈，天真了~~