第 5 天
双指针
876. 链表中间结点
给定一个头结点为head返回链表中间结点的非空单链表。
若有两个中间结点，则返回第二个中间结点。
[1，2，3，4，5] 列表中的结点 3 (序列化形式:[3，4，5]) 返回的结点值为 3 。 (评估系统对结点序列化的表达 [3，4，5])。 注意，我们回来了 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
[1，2，3，4，5] 列表中的结点 4 (序列化形式:[4，5，6]) 由于列表有两个中间结点，值分别为 3 和 4.我们返回第二个结点
# 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: n = 1 tem = head while tem.next != None: tem = tem.next n = 1 n = n//2 tem = head for i in range(n): tem = tem.next return tem思路：先遍历链表，统计链表长度，然后在找到中间位置给另一个节点。
该方法具有较高的时间和空间复杂性
19. 删除链表倒数第 N 个结点
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: temn = tem = ListNode() temn.next = tem.next = head # if tem.next.next == None: # return None for i in range(n): temn = temn.next while temn.next: tem = tem.next temn = temn.next new = tem.next.next if tem.next == head: head = new else: tem.next = new return head