打败算法 —— 删除链表的倒数第n个结点

本文参考

出自LeetCode上的题库 —— 删除链表的倒数第n个结点，官方的双指针解法没有完全符合"只遍历一遍链表"的要求，本文给出另一种双指针解法

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

删除倒数结点问题

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

解题思路

第一种解法，先遍历一遍原列表，记录链表长度，然后再遍历一遍就能够删除对应的结点

第二种解法利用双指针，我们"回文链表"（https://www.cnblogs.com/kuluo/p/15955593.html）中通过双指针找到中间节点（slow指针所在的位置），因此也能够计算链表的长度。获取到链表的长度后，根据倒数第n个结点是在slow指针前还是在slow指针后，决定是从head头节点开始找，还是从slow指针所指的结点开始找，相当于减少了一半的结点遍历过程

在这道题中，我们看到双指针不但能够使算法保持在$O(n)$的时间复杂度，也能将空间复杂度限制在常数级$O(1)$

双指针解法

class ListNode:

def __init__(self, val=0, next=None):

self.val = val

self.next: ListNode = next
class Solution:

def remove_Nth_from_end(self, head: ListNode, n: int) -> ListNode:

cnt = 1

slow = fast = head

# 通过快慢指针获得链表长度

while fast.next and fast.next.next:

cnt += 1

slow = slow.next
fast = fast.next.next

# 计算链表长度

if fast.next is None:

length = cnt * 2 - 1

else:

length = cnt * 2

# 特殊情况

if n == length:

return head.next

# 链表的前半部分
# length = 5, n = 2, step = 5 - 2 - 3 + 1 = 1

if n > length / 2:

step = length - n
curr = pre = head

# 链表的后半部分

else:

step = length - n - cnt + 1

curr = pre = slow

# 获得步长后移动到特定位置并删除指针

for i in range(step):

pre = curr
curr = curr.next
curr = curr.next
pre.next = curr

return head

巴特西

打败算法 —— 删除链表的倒数第n个结点

最新文章

热门文章