面试必刷TOP101：链表（06-10，Python实现）
6.判断链表是否有环（小试牛刀）
class Solution:
def hasCycle(self , head: ListNode) -> bool:
if head == None:
return False
p = head
q = head
while p != None and p.next != None:
p = p.next.next
q = q.next
if p == q:
return True
return False
时间复杂度：O(n)，最坏情况下遍历链表 n 个结点
空间复杂度：O(1)，仅使用两个指针，没有额外辅助空间
7.链表中环的入口结点（小试牛刀）
class Solution:
def hasCycle(self, head):
if head == None:
return None
p = head
q = head
while p != None and p.next != None:
p = p.next.next
q = q.next
if p == q:
return q
return None
def EntryNodeOfLoop(self, pHead):
q = self.hasCycle(pHead)
if q == None:
return None
p = pHead
while p != q:
p = p.next
q = q.next
return p
8.链表中倒数最后k个结点（小试牛刀）
8.1 快慢双指针法
class Solution:
def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
p = pHead
q = pHead
for i in range(0,k):
if p == None:
return None
p = p.next
while p != None:
p = p.next
q = q.next
return q
时间复杂度：O(n)，总共遍历 n 个链表元素
空间复杂度：O(1)，无额外空间使用
8.2 先找长度再找最后k
class Solution:
def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
n = 0
p = pHead
while p != None:
n = n + 1
p = p.next
if n < k:
return None
p = pHead
for i in range(0,n-k):
p = p.next
return p
时间复杂度：O(n)，最坏情况下两次遍历 n 个链表元素
空间复杂度：O(1)，无额外空间使用
9.删除链表的倒数第 n 个结点（小试牛刀）
9.1 双指针
class Solution:
def removeNthFromEnd(self , head: ListNode, n: int) -> ListNode:
res = ListNode(-1)
res.next = head
fast = head # 一直往前走
p = head
q = res
for i in range(0,n):
fast = fast.next
while fast != None:
fast = fast.next
q = p
p = p.next
q.next = p.next
return res.next
时间复杂度：O(n)，其中 n 为链表长度，最坏情况遍历整个链表 1 次
空间复杂度：O(1)，常数级指针，无额外辅助空间使用
9.2 长度统计法
时间复杂度：O(n)，其中 n 为链表长度，最坏情况遍历整个链表 2 次
空间复杂度：O(1)，常数级指针，无额外辅助空间使用
10.两个链表的第一个公共结点（小试牛刀）
10.1 双指针长度比较法
class Solution:
def FindFirstCommonNode(self , pHead1 , pHead2 ):
p = pHead1 ; m = 0
q = pHead2 ; n = 0
while p != None:
m = m + 1
p = p.next
while q != None:
n = n + 1
q = q.next
if m >= n:
k = m - n
for i in range(0,k):
pHead1 = pHead1.next
while pHead1 != None and pHead2 != None and pHead1 != pHead2:
pHead1 = pHead1.next
pHead2 = pHead2.next
else:
k = n - m
for i in range(0,k):
pHead2 = pHead2.next
while pHead1 != None and pHead2 != None and pHead1 != pHead2:
pHead1 = pHead1.next
pHead2 = pHead2.next
return pHead1
时间复杂度：O(n)，其中 n 为两链表较长者的长度，虽是多次循环，但都为单循环，取最大值即为 O(n)
空间复杂度：O(1)，没有其他空间申请
10.2 双指针连接法
class Solution:
def FindFirstCommonNode(self , pHead1 , pHead2 ):
p = pHead1
q = pHead2
while p != q:
if p == None:
p = pHead2
else:
p = p.next
if q == None:
q = pHead1
else:
q = q.next
return p
时间复杂度：O(n+m)，其中 m 与 n 分别为两链表的长度，因一次遍历两链表，所以为 O(n+m)，也可以看成是 O(n) 级别的。
空间复杂度：O(1)，没有其他空间申请。