数据结构 链表(第7、8天)

链表

这里面的链表题比较简单，只要会遍历链表、删除链表节点、反转链表这些基本操作就行。
必要时可以画图辅助理解。

141.环形链表

给定一个链表，判断是否有环。
思路：快慢指针。 快指针每次走两步，慢指针每次走一步。
如果某个时刻两个指针相遇，说明有环。
原理可以看官方题解，简单来说就是如果存在一个环，那么快指针和慢指针一定会掉到环里，在这个环里跑步，一快一慢总是会相遇的。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        fast, slow = head, head
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

21. 合并两个有序链表

这个没啥好说的，就是遍历一下。

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        if  list2 is None:
            return list1
        elif list1 is None:
            return list2

        cur = dummy

        while list1 is not None and list2 is not None:
            if (list1.val <= list2.val):
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next

        if list1 is not None:
            cur.next = list1
        elif list2 is not None:
            cur.next = list2

        return dummy.next

203. 移除链表元素

删除所有值=val的节点。

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if not head:
            return head
        dm = ListNode(0,head)
        tm = dm
        while tm.next:
            if tm.next.val == val:
                tm.next = tm.next.next
            else:
                tm = tm.next
        return dm.next

206. 反转链表

反转链表，利用递归方法比较容易。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return  head

        res = self.reverseList(head.next) #剩下的
        head.next = None #断开第一个
        t = res
        while  t.next != None:
            t = t.next
        t.next = head #剩下的+第一个
        return  res

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

注意是排序链表，所以重复元素一定相邻。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        h = head
        
        while head.next:
            if head.val == head.next.val:
                head.next = head.next.next
            else:
                head = head.next
                

        return h