【LeetCode】删除链表的倒数第N个节点（python）

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

解题思路
通过一次遍历链表的方式进行实现，可以通过一个数组存储链表的值（以空间换时间）：

		result = []
        while head:
            result.append(head.val)
            head = head.next

然后删除数组中倒数第n个节点：

result = result[0: len(result) - n] + result[len(result) - n + 1: len(result)]

最后，将数组中剩下的元素构成新的链表，返回即可。

		new_h = ListNode(result[0]) 
        new_c = new_h
        for i in range(1, len(result)):
	            temp = ListNode(result[i])
	            new_h.next = temp
	            new_h = new_h.next

完整代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if not head or n < 0:
            return None
        result = []
        while head:
            result.append(head.val)
            head = head.next
        if n > len(result):
            return None
        result = result[0: len(result) - n] + result[len(result) - n + 1: len(result)]
        if len(result) == 0:
            return None
        new_h = ListNode(result[0]) 
        new_c = new_h
        for i in range(1, len(result)):
            temp = ListNode(result[i])
            new_h.next = temp
            new_h = new_h.next
        return new_c