NO.141 环形链表

题目链接
在这里插入图片描述

方法一：遍历并存储节点到哈希表，如果出现重复节点，证明该链表有环

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while (head):
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

方法二：快慢指针，一个指针快，一个指针慢，如果链表有环，快的指针一定会追上慢的指针;注意不要忘记判断链表是否结束

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next : 
            return False
        slow = head
        fast = head.next
        while(slow!=fast):
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

关于快慢指针链接

请添加图片描述

NO.21 合并两个有序链表

在这里插入图片描述

方法一：（归并排序思想;递归）

题目理解：（于评论区发现这一通俗解释）
在这里插入图片描述

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 归并排序思想
        # l1 为空时，列表为l2剩余部分；l2为空时，列表为l1剩余部分
        if not list1: return list2
        if not list2: return list1
        # 数组升序合并
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2