请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。**传入函数的唯一参数为 要被删除的节点** 。

* 链表至少包含两个节点。

* 链表中所有节点的值都是唯一的。

* 给定的节点为非末尾节点并且一定是链表中的一个有效节点。

* 不要从你的函数中返回任何结果。

输入：head = [4,5,1,9], node = 5

输出：[4,1,9]

解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

与之前做过的一个题目很像，[移除链表元素（两个指针）](移除链表元素.md)，

但之前做的题目的参数包括链表本身，以及要删除的目标元素，可以通过迭代链表，通过前继节点与当前节点两个索引来完成。

本题目只知道唯一参数是要被删除的节点。

我们将要删除节点的 next 节点的值赋值给要删除的节点，转而去删除 next 节点，从而达成目的。

4->5->1->9 node = 5

def deleteNode(node):

node.val = node.next.val

node.next = node.next.next

请判断一个链表是否为回文链表。

输入: 1->2->2->1

输出: true

输入: 1->2

输出: false

把链表转成列表，通过列表判断是否回文

def isPalindrome(head):

val_list = []

cur = head

while cur:

val_list.append(cur.val)

cur = cur.next

return val_list == val_list[::-1]

给定一个头结点为 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.

**两次遍历**

* 第一次遍历链表，得到链表长度，计算中间节点的位置

* 第二次遍历链表，到中间节点就返回

def middleNode(self, head: ListNode) -> ListNode:

count = 0

cur = head

while cur:

count += 1

cur = cur.next

mid = int(count/2 + 1)

count = 0

cur = head

while cur:

count += 1

if count == mid:

return cur

cur = cur.next

**一次遍历**

def middleNode(head):

A = [head]

while A[-1].next:

A.append(A[-1].next)

mid = len(A)//2

return A[mid]

**快慢指针**

用两个指针slow与fast一起遍历链表。slow 一次走一步，fast一次走两步。那么当fast到达链表的末尾时，slow必然位于中间。

def middleNode(head):

slow = head

fast = head

while fast and fast.next:

slow = slow.next

fast = fast.next.next

return slow