面试必刷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
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：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
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度：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
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(n+m)，其中 m 与 n 分别为两链表的长度，因一次遍历两链表，所以为 O(n+m)，也可以看成是 O(n) 级别的。
空间复杂度：O(1)，没有其他空间申请。