[数据结构与算法]链表做题总结（三）[8692][141142138]

138. 复制带随机指针的链表

思路：采用哈希表进行两次遍历。第一次遍历将拷贝后链表的每个节点与原链表一一对应。第二遍遍历将哈希表中 value的next指针 指向cur的next节点在哈希表中对应的vaule
注意：用get而不是map1[cur.next]。因为会到None
代码：

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return head
        map1 = {}
        cur = head
        while cur:
            map1[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            map1[cur].next = map1.get(cur.next) #重点！！注意，这个地方用get而不是map1[cur.next]。因为会到None
            map1[cur].random = map1.get(cur.random)#这个点，而哈希表里面是没有None的，就会报错。所以用get，如果出现None就返回一个空值
            cur = cur.next
        return map1[head]

141.环形链表

. 复制带随机指针的链表

思路：采用哈希表或快慢指针，根据题目O(1)的要求，快慢指针更合适
注意：在快慢指针方法中，需要注意while循环条件。快指针每次走两步，慢指针每次走一步，若有环，两者终会相遇。
代码：

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        hashmap={}
        cur = head

        while cur:
            if cur in hashmap:
                return True
            hashmap[cur]=cur.val

            cur = cur.next
        return False

# 快慢指针
        if not head or not head.next:
            return False
        fast = head.next
        slow = head

        while fast != slow:
            if not fast or not fast.next:
                return False
            slow=slow.next
            fast=fast.next.next
        return True

142. 环形链表 II

思路：与上一题相似，但是多了返回入环节点的要求。利用数学思维，结合快慢指针，
注意：需要注意在遍历快慢指针时while循环条件。最开始slow和fast都指向head,这样才符合最后数学公式的推导。
代码：

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return
        slow = head
        fast = head

        while True:
            if not fast or not fast.next:
                return
            slow=slow.next
            fast=fast.next.next

            if fast==slow:
                break

        ptr = head
        while ptr!=slow:
            ptr=ptr.next
            slow=slow.next
        return slow