LeetCode刷题笔记（二）链表

二. 链表

Leetcode中的链表有一个ListNode类，我很好奇它是怎么实现的？还有树的TreeNode类。上述两者，我没有找到具体实现的代码，有人知道欢迎评论告知，感谢。
链表题的边界条件问题有一个很巧的避免方法，就是在head节点前加一个哑巴节点dummy-node。第21题和第83题都用了哑巴节点。

21. 合并两个有序链表

题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(-1)
        prev = dummy
        while l1 and l2: # 依次赋值给next
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next            
            prev = prev.next
        if l1 is not None:# 将链表末尾指向未合并完的剩余的链表
            prev.next = l1
        else:
            prev.next = l2
        return dummy.next

83. 删除排序链表中的重复元素

题目：存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
输入：head = [1,1,2]
输出：[1,2]

    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy = ListNode(-999) # 哑巴节点
        dummy.next = head
        cur = dummy
        while cur != None and cur.next != None: # 不停循环并保证下一个节点存在
            if cur.val == cur.next.val: # 如果当前节点等于下一个节点
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

141. 环形链表

题目：给定一个链表，判断链表中是否有环。
输入：head = [3,2,0,-4], pos = 1
输出：True
思考：fast比slow每次都快1步，那迟早能追上。

    def hasCycle(self, head: ListNode):
        fast = slow = head # 快慢指针法
        while slow and fast and fast.next: # 循环，并保证快指针的下一个节点不为空
            slow = slow.next
            fast = fast.next.next
            if slow is fast: # 快慢指针迟早会在环上相遇，Floyd 判圈算法
                return True
        return False

160. 相交链表

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A, B = headA, headB # 假设A的节点为a+n个，B的节点数是b+n个
        while A != B:  # 一共循环a+b+n次后会相遇
            if A: 
                A = A.next  # A不停向后迭代。
            else: 
                A = headB 
            if B: 
                B = B.next # B不停向后迭代。
            else: 
                B = headA
        return A

203. 移除链表元素

题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
思考：这道题目和83题一模一样的解题模板。

    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(-99999) # 哑巴节点
        dummy.next = head
        cur = dummy
        while cur != None and cur.next != None: # 不停循环，保证存在下一个节点
            if cur.next.val == val: # 如果当前节点等于某个值
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

206. 反转链表

题目：单链表反转
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

    def reverseList(self, head: ListNode) -> ListNode:
        cur, prev = head, None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next # 别想太多，这题直接背下来
        return prev

234. 回文链表

题目：请判断一个链表是否为回文链表。
输入：1->2->2->1
输出：True

    def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        cur = head
        while cur is not None:
            vals.append(cur.val)
            cur = cur.next
        return vals == vals[::-1]

237. 删除链表中的节点

题目：请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]

    def deleteNode(self, node): # 很奇怪这里没有输入head，只输入了node
        node.val = node.next.val # 那就把node完整置换成node.next就行了
        node.next = node.next.next