19、删除链表的倒数第N个结点
文章出现的代码都是python3
题目
给你一个链表，删除链表的倒数第n个结点，并返回链表的头结点
示例1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例2：
输入：head = [1], n = 1
输出：[]
示例3：
输入：head = [1,2], n = 1
输出：[1]
思路
要删除倒数第n个结点，需要找到倒数第n个结点的前驱结点，删除其的下一个结点即可。而链表的长度是未知的，所以第一想法就是先计算链表的长度，然后再找到第n个结点。还有一种方法就是使用快慢指针，这样当快指针走到尾结点的时候，此时只需要满指针刚好走到倒数第n个结点，或者倒数第n个结点的前驱结点即可
解法1
先计算链表长度，然后找到第n个结点的前驱结点，删除即可。
class Solution:
# 获取链表长度
def getLinkedLength(self, root: ListNode):
l, cur = 0, root
while cur:
l += 1
cur = cur.next
return l
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if not head: return head
pre = self.getLinkedLength(head) - n
# 创建虚拟头结点，处理删除头结点的情况
vHead = ListNode(0, head)
cur = vHead
while pre:
cur = cur.next
pre -= 1
cur.next = cur.next.next
return vHead.next
解法2
使用快慢指针，快指针比慢指针多走n+1个长度，那么当快指针走到尾结点的时候，慢指针刚好走到要删除的前驱结点。
class Solution:
def removeNthFromEnd1(self, head: ListNode, n: int) -> ListNode:
# 创建虚拟头结点，处理删除头结点的情况
vHead, fast = ListNode(0, head), head
# 将慢指针指向虚拟头结点
slow = vHead
while n:
fast = fast.next
n -= 1
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return vHead.next
2130、链表最大孪生和
题目：
在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
- 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
孪生和 定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。
示例1：
输入：head = [5,4,2,1]
输出：6
示例2：
输入：head = [4,2,2,3]
输出：7
思路：
这道题很容易想到将后半部分进行反转，然后找出最大和
class Solution:
# 获取链表终点
def getMedian(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 反转链表
def reversed(self, head):
prev, cur = None, head
while cur:
next =cur.next
cur.next = prev
prev = cur
cur = next
return prev
def pairSum(self, head: Optional[ListNode]) -> int:
if not head: return 0
# 获取到反转链表
last = self.reversed(self.getMedian(head))
ans = 0
# 取节点和的最大值
while head and last:
ans = max(head.val + last.val, ans)
head = head.next
last = last.next
return ans
