目录
🍟解读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