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