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思路。