LeetCode刷题实战19：删除链表的倒数第N个节点
共 3062字，需浏览 7分钟
·
2020-08-24 02:55
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做删除链表的倒数第N个节点 ，我们先来看题面：
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
Given a linked list, remove the n-th node from the end of list and return its head.
题意
样例
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
题解
两次遍历
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
l = 0
pnt = head
# 计算链表长度
while pnt:
l += 1
pnt = pnt.next
# 如果长度为1，直接return None
if l == 1:
returnNone
# 计算删除需要移动的长度
l = l - n - 1
# 如果小于0，说明需要删除第一个元素，那么直接return head.next。
if l < 0:
return head.next
pnt = head
for i in range(l):
pnt = pnt.next
pnt.next = pnt.next.next
return head
一次遍历
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
pnt1 = head
# 第一个指针先跑n步
for i in range(n):
pnt1 = pnt1.next
# 注意，如果是删除head，会出现跑过头的情况，需要判断
if pnt1 isNone:
return head.next
pnt2 = head
# 移动第一个指针，直到结尾
while pnt1.next:
pnt1 = pnt1.next
pnt2 = pnt2.next
# 删除pnt2.next位置的节点
pnt2.next = pnt2.next.next
return head
上期推文：