[数据结构与算法]力扣19. 删除链表的倒数第 N 个结点---Python

19. 删除链表的倒数第 N 个结点

题目描述：

给你一个链表，删除链表的倒数第 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]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：
遍历一遍链表，记录链表中节点的总数目以及要删除的节点位置，就简单许多了，要考虑一些细节：
（1）链表中节点总数目为1：返回为空（因为n的值最小是1）
（2）要删除的节点在第一个：返回第二个节点
（3）要删除的节点在最后一个：将倒数第2的节点的next置空

AC代码：

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


class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        pos = head
        ans, cnt = [], 0
        # 将每个节点存储在列表里面
        while pos:
            cnt += 1
            ans.append(pos)
            pos = pos.next
        if cnt == 1:
            return None
        if n == cnt:  # 若删除的节点在最左边
            return head.next
        elif n == 1:  # 若删除的节点在最右边
            temp = ans[cnt - 2]
            temp.next = None
        else:
            temp, temp1 = ans[cnt - n - 1], ans[cnt - n + 1]
            temp.next = temp1
        return head


# 测试数据
ss = Solution()
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
ans = ss.removeNthFromEnd(head, 1)
while ans:
    print(ans.val)
    ans = ans.next