【Leetcode_总结】19. 删除链表的倒数第N个节点- python
Q:
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/
思路:先求长度,然后再依次将节点相连,略过倒数第n个节点
代码:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
stack=[]
pre = head
while pre.next:
stack.append(pre)
pre = pre.next
stack.append(pre)
if (len(stack)) == n:
return head.next
del_num = len(stack)-n
head_ = new = stack.pop(0)
new.next = None
tmp = 1
flag = True
while stack:
if tmp == del_num and flag:
stack.pop(0)
flag = False
else:
new.next = stack.pop(0)
tmp += 1
new = new.next
new.next = None
return head_