目录
🍟解读while为什么判断fast.next 和fast？而不是fast.next.next 和fast.next ?
🍕题目
🍔方法一：
这里借用一下题解里的图
通过数组访问，我们可以发现个结论：中间节点在数组的索引为N/2
🍟代码
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def middleNode(self, head: ListNode) -> ListNode: A = [head] while A[-1].next: A.append(A[-1].next) return A[len(A) // 2]
🍔方法二：快慢指针法
两个指针
slow与fast一起遍历链表。slow一次走一步，fast一次走两步。那么当fast到达链表的末尾时，slow必然位于中间。这里我借用题解的图
拿例题来说
🍟代码：
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def middleNode(self, head: ListNode) -> ListNode: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow
🍟解读while为什么判断fast.next 和fast？而不是fast.next.next 和fast.next ?
liweiwei1419大佬的图
因为题目如果有两个中间结点，则返回第二个中间结点！！！
判断fast.next 和fast
fast.next.next 和fast.next
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def middleNode(self, head: ListNode) -> ListNode: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow
🍕题目
🍔方法一：暴力解法
1）找到链表长度
2）删除从表头开始的（L-n+1）节点
技巧：
在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了
为了与题目中的 n保持一致，节点的编号从 1 开始，头节点为编号 1的节点。
为了方便删除操作，我们可以从哑节点开始遍历 L-n+1个节点。当遍历到第 L-n+1 个节点时，它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除操作。
🍟代码
class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: def getLength(head: ListNode) -> int: length = 0 while head: length += 1 head = head.next return length dummy = ListNode(0, head) length = getLength(head) cur = dummy for i in range(1, length - n + 1): cur = cur.next cur.next = cur.next.next return dummy.next
🍔方法二：双指针
由于我们需要找到倒数第 n个节点，因此我们可以使用两个指针first 和 second同时对链表进行遍历，并且firstt 比 second超前 n个节点。当 first遍历到链表的末尾时，second 就恰好处于倒数第 n个节点。
在这之后，我们同时使用first 和second 对链表进行遍历。当first 遍历到链表的末尾（即 first 为空指针）时，second 恰好指向倒数第 n 个节点。
🍟 代码
class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: dummy = ListNode(0, head) first = head second = dummy for i in range(n): first = first.next while first: first = first.next second = second.next second.next = second.next.next return dummy.next
