力扣刷题日常

876快慢指针问题说明了快慢指针的一个性质。如果我们需要慢指针指向中间节点或者中间偏右的节点我们就可以用快慢指针去实现。快指针走两步慢指针走一步。然后当快指针指向空或者快指针的下一个为空的时候我们返回慢指针就可以得到一半的指针了# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def middleNode(self, head: Optional[ListNode]) - Optional[ListNode]: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow141.环形链表的问题这里用到了一个判断条件就是当fast不满足while退出条件的时候我们可以不断地去判断fast是否等于slow判断成功了就可以返回true否则要是循环已经结束还是没有环那就是false。# 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: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if fast slow: return True return False142.环形链表问题2当我们需要去判断环形链表的进入节点的时候。我们可以用一个快慢链表先找到在环形链表中第一次相遇的位置然后让头结点跟慢指针都一起挪动当两个位置相同的时候就是始发点了。具体来说: 设头到转的地方为a 转到第一次相遇地为b快慢第一次相遇到转的地方为c。然后我们就可以得到2(ab) (ab) k(bc) 其中ab是慢指针步数。2(ab)是快指针转的总步数。bc是一圈的圈数。最后可以得出 a-c (k-1)(bc)即我们的头结点跟着慢节点走c步慢节点刚好到了转的点。头结点与慢节点之间刚好a-c的距离。所以有以下的代码# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: fast head slow head while fast and fast.next: slow slow.next fast fast.next.next if fast slow: while slow ! head: head head.next slow slow.next return slow return None143.重排链表这一题综合了我们昨天跟今天所学的知识。我们可以把步骤解构。1.我们需要找到链表的中间节点然后基于中间节点去对后面的内容做反转。然后这里的难点就是我们需要什么时候终止链表排序。这里给出来的是head2.next为空的时候。我们可以得出来head2为最后一个元素的时候其实我们是不需要的因为这个元素在原链表中也是存在的我们只需要去保存原链表中的内容就可以了所以我们的条件是head2.next。# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def reorderList(self, head: Optional[ListNode]) - None: Do not return anything, modify head in-place instead. def find_mid(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow def reverse_list(head): cur head pre None while cur: nxt cur.next cur.next pre pre cur cur nxt return pre mid find_mid(head) head2 reverse_list(mid) while head2.next: nxt head.next nxt2 head2.next head.next head2 head2.next nxt head nxt head2 nxt2237.删除链表中的节点我们需要进行一个复写删除的操作。什么意思呢就是先把要删除的节点变成下一个节点的内容然后把跳过下一个节点。# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def deleteNode(self, node): :type node: ListNode :rtype: void Do not return anything, modify node in-place instead. node.val node.next.val node.next node.next.next19. 删除链表中的第n个节点这一题其实考察的是怎么找到第n1个节点的位置。我们可以让右指针先走n步然后再让左指针一起出发来实现。这一题需要用到哨兵指针dummynode因为如果不用的话我们需要删除头节点的时候会有问题。所以哨兵指针需不需要设置取决于头节点会不会发生改变。# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: dummy ListNode(nexthead) right dummy left dummy for _ in range(n): right right.next while right.next: left left.next right right.next left.next left.next.next return dummy.next83.删除排序链表中的重复元素。这一题我们需要想清楚的是1.我们做到什么时候结束 2.什么时候我们需要去跳过。首先第一个问题我们当然是一直处理直到后面没有节点为止。所以我们设置一个cur表示当前处理的节点的位置指针。当cur.next指向为空的时候停止也就是cur指向最后一个节点的时候停止。当然他会把最后一个节点的事情处理的代码如下图所示# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: if head is None: return head cur head while cur.next: if cur.val cur.next.val: cur.next cur.next.next else: cur cur.next return head82删除排序链表中的重复元素这一题需要删除所有的重复元素我们首先需要设置一个dummy哨兵因为头节点可能会被删除掉所以我们需要去设置一个哨兵节点。然后题目中最有意思的就是循环的部分了我们的操作什么时候停止呢题目中要的是不出现重复最小不重复的判断其实就是两个元素所以我们循环当cur.next 和 cur.next.next 都存在的时候可以运行如果只有一个元素的话循环就中止了。所以我们这里最外面的循环是cur.next 和 cur.next.next。然后到了下面第二部分如何删光这重复的内容我们需要知道的是cur指向的是安排好的处理好的元素而下面两个元素的指针是不确定的。我们需要去更新下面两个指针使得我们可以去更新cur。这里就说明了当两个指针的值是一样的时候我们需要更新cur.next让他看看到底重复到哪里这个地方需要一个while循环以保证cur.next更新到了不同的值了。下面就来看看代码怎么具体实现# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(nexthead) cur dummy while cur.next and cur.next.next: val cur.next.val if cur.next.val cur.next.next.val: while cur.next and cur.next.val val: cur.next cur.next.next else: cur cur.next return dummy.next