leetcode链表之倒数第N个结点

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