多种解法破解链表
- 2019 年 10 月 5 日
- 笔记
多种解法破解链表
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
但是可惜这个方法通不过，他不允许修改链表结构，哈哈，天真了~~
