给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 具体题目链接
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指针也将达到中心位置。
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思路,也是快慢指针。
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 进阶:你能尝试使用一趟扫描实现吗? 具体题目链接
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节点到达需要剔除的节点前一个节点,通过修改该节点的指向来实现剔除效果。下面时自己做的动画。
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思路。