分类刷题：链表的查找

分类刷题的第二天：

JZ23 链表中环的入口结点

思路：

最常规易懂的解法就是遍历整个链表结点，然后用哈希表来存储已访问过的结点，最后进行对比。 若该结点已存在哈希表中，则代表该结点是我们要找的环形链表的入口结点；否则把结点添加到哈希表中，继续往下遍历。

    def EntryNodeOfLoop(self, pHead):
        # write code here
        dict = {}
        i = 0
        while pHead:
            if pHead.val not in dict:
                dict[i] = pHead.val
                pHead = pHead.next
                i += 1
            else:
                return pHead.val

纠正：

1. 首先第七行用dict[i]=pHead.val其中的i没有实际存在的意义，相当于给遍历到的元素value加上了一个key，所以可以不用dict，只用set来保存value，而不加上key。而且dict的内存比set要大很多，经过修改发现用dict会超过内存。

（补充set和dict的区别：https://www.cnblogs.com/chenwolong/p/dict.html）

2. 哈希表中增加元素直接用add， nodes.add(pHead)。

按照上述思想对源代码进行改进：

不太明白为什么原来都要node.val而这边说是个int的结构，留一下

继续修改：

    def EntryNodeOfLoop(self, pHead):
        # write code here
        dict = set()
        i = 0
        while pHead:
            if pHead not in dict:
                dict.add(pHead)
                pHead = pHead.next
                i += 1
            else:
                return pHead

复现的时候，没看懂为啥要设置一个毫无作用的i

要注意啊，虽然这次浮现记住了要用set()，但是还是忘记了怎么使用set类似于list里append的功能，要经常去复习add

第一遍复现：

    def EntryNodeOfLoop(self, pHead):
        # write code here
        dict = set()
        while pHead:
            if pHead not in dict:
                dict.add(pHead)
                pHead = pHead.next
            else:
                return pHead

解法2：快慢双指针

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        #创建快、慢两种指针
        fast, slow = pHead, pHead
        while True:
            #第一种结果： fast 指针走过链表末端，说明链表无环，返回 None
            if not fast or not fast.next:
                return None            
            #慢指针一次走一步；快指针一次两步
            slow = slow.next
            fast = fast.next.next
            #如果有环，第一次相遇：
            if slow == fast:
                break
        #第二次相遇,fast回到链表起点位：
        fast = pHead
        #fast、slow两指针不相遇的时候都各走一步：
        while slow != fast:
            fast = fast.next
            slow = slow.next
        #再次相遇即slow所在节点
        return slow 

反正我写不出来

JZ22 链表中倒数最后k个结点

自己的解法：

    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        def length(pHead):
            count = 0
            while pHead:
                pHead = pHead.next
                count += 1
            return count
        n = length(pHead)
        if k > n:
            return None
        else:
            for _ in range(n-k):
                pHead = pHead.next
            return pHead

注意： 首先，要熟悉length函数的写法，记住count从0开始遍历；

其次要注意直接print pHead就行了，pHead不是一个节点，是一个链表，也就是说后面还有一串。

解法2：快慢指针

    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        fast = pHead
        slow = pHead
        #快指针先行k步
        for i in range(0,k): 
            if fast != None:
                fast = fast.next
            #达不到k步说明链表过短，没有倒数k
            else: 
                return None
        #快慢指针同步，快指针先到底，慢指针指向倒数第k个
        while fast:
            fast = fast.next
            slow = slow.next
        return slow