leetcode第19题:删除链表的倒数第N个节点
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
【题目】
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
【思路】
解法一:遍历链表,得到链表长度N。那么删除倒数第n个节点,即为删除第N - n个节点。找到第N - n -1个节点,记为p,q = p.next, p.next=p.next.next, del p(记得清除内存)。
唯一的问题是:如何删除第1个元素,需要单独判断?可以不用这么麻烦:增加一个无意义的头结点,所有的删除逻辑都变成一致的了!
解法二:使用两个指针first和second遍历链表,首先,first指针前进n步,second指针不变;紧接着,first指针和second指针同时前进,直到first.next为None。此时,second指针指向的是倒数第n+1个节点,second.next = second.next.next同时删除无用内存即可。(删除第1个元素的代码逻辑与其它元素的不一样,解决方法参考解法一的说明。)
【代码】
python版本
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 增加空的头结点,使得逻辑一致
node = ListNode(val=0, next=head)
head = node
# 找到第n-1个节点
count = 0
p = head
while count < n:
count += 1
p = p.next
# 找到倒数第n+1个节点
q = head
while p.next:
p = p.next
q = q.next
# 删除倒数第n个节点
r = q.next
q.next = q.next.next
del r
return head.next
【相似题目】
82. 删除排序链表中的重复元素 II
解题思路:先得到重复的元素值,再根据值删除节点。
83. 删除排序链表中的重复元素
解题思路:p.val = p.next.val,则删除p.next。
203. 移除链表元素
解题思路:p.next.val == target,则删除p.next。
237. 删除链表中的节点
解题思路:p.next == node,则删除p.next