Python删除单链表倒数第n个节点

链表的表示方法除使用两个列表的方法外,还可以使用对象的方式。

例如下面的类:
#节点定义
class ListNode:
def __init__(self, v):
    self.val = v
    self.next = None
类的 val 属性存储数据,next 属性存储下一个节点。

现在的问题是,给定一个链表,删除链表的倒数第 n 个节点。例如,链表为 1→2→3→4→5,删除倒数第三个数据后链表变为 1→2→4→5。分析下问题,可得知想要删除倒数第 n 个数据,只需要把倒数第 n-1 个节点的 next 值改为第 n+1 个节点即可。那么问题就变成了如何找到第 n-1 个节点的问题。

首先,我们需要创建两个指针 fast 和 slow,同时为了防止出现倒数第 n 个节点正好是第一个节点的特殊情况,需要先创建一个临时节点作为头节点,并把两个指针都赋值为链表的头节点,如下:
#删除倒数第n个数据
def removeLastNth(head, n):
    temp = ListNode(0)
    temp.next = head
    fast = slow = temp

然后,让 fast 指针先走 n 步,slow 指针保持原地不动。
while c < n: #fast先走n步
    fast = fast.next
    c += 1

接下来,让 fast 指针和 slow 指针同时移动,当 fast 指针指到最后一个元素时,那么 slow 指针指向的元素即为倒数第 n-1 个节点。
while fast.next:
    fast = fast.next
    slow = slow.next

经过前面的操作,slow 指针已经指向倒数第 n-1 个节点,最后,让 slow 指针指到它的下一节点的下一个节点,即删除倒数第 n 个节点,代码如下:
slow.next = slow.next.next

本问题的核心思想是通过两个指针寻找倒数第 n-1 个节点,再删除第 n 个节点,完整代码如下:
#节点定义
class ListNode:
def __init__(self, v):
    self.val = v
    self.next = None
#删除倒数第n个数据
def removeLastNth(head, n):
    temp = ListNode(0)
    temp.next = head
    fast = slow = temp
    c = 0
    while c < n:        #fast指针先走n步
        fast = fast.next
        c += 1
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
return temp.next