LeetCode-算法-双指针-第5天
876. 链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 具体题目链接
Python
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
ans,n=head,0
while ans:
n+=1
ans=ans.next
ans,t=head,0
while t<n//2:
t+=1
ans=ans.next
return ans思路：这是我第一开始的思路，并没用用到双指针，通过while进行一次遍历统计列表的长度，在通过第二次while循环找出中心点指针。
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
slow,fast=head,head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
return slow思路：这个思路是双指针中的快慢指针，fast指针每前进两步，slow指针前进一步，这样当fast指针结束时，slow指针也将达到中心位置。
GO
func middleNode(head *ListNode) *ListNode {
slow,fast:=head,head
for fast!=nil &&fast.Next!=nil{
slow=slow.Next
fast=fast.Next.Next
}
return slow
}思路：参考第二个python思路，也是快慢指针。
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 进阶：你能尝试使用一趟扫描实现吗？ 具体题目链接
Python
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
newlist=ListNode()
newlist.next=head
slow=fast=newlist
while fast:
fast=fast.next
if n<0:
slow=slow.next
else:
n-=1
slow.next=slow.next.next
return newlist.next思路：首先先创建一个虚拟节点指向head，保证我们可以修改head内容。它规定是删除倒数第n个节点，那么fast节点就要比slow节点快n个节点，这样能保证当fast节点到达最后一个时，slow节点到达需要剔除的节点前一个节点，通过修改该节点的指向来实现剔除效果。下面时自己做的动画。
快慢指针
GO
func removeNthFromEnd(head *ListNode, n int) *ListNode {
newlist := &ListNode{}
newlist.Next=head
fast,slow:=newlist,newlist
for fast!=nil{
if n<0{
slow=slow.Next
}else{
n--
}
fast=fast.Next
}
slow.Next=slow.Next.Next
return newlist.Next
}思路：请看python思路。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021年07月29日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
