本文主要是介绍Leetcode 19. 删除链表的倒数第N个节点 ----python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 题目描述
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
2.解题思路
这题要分情况讨论
（1）当链表为空或只有一个节点时，返回结果为None
（2）当删除的元素为链表首元素时，返回head.next
（3）其他情况，定义快慢指针（fast,slow）,快指针先走n步，然后快慢指针一起走直到fast指向为 空，然后删除show指向的节点。
3. 代码实现
class Solution:def linkLength(self, root):length = 0r = rootwhile (r):length = length + 1r = r.nextreturn lengthdef removeNthFromEnd(self, head, n):if(head == None or head.next == None):return Noneif(self.linkLength(head) == n):return head.nextroot1 = headfast = headslow = headfor i in range(0, n): #fast指针向后移动n个元素fast = fast.nextwhile(fast):#快慢指针同时移动beforeSlow = slowslow = slow.nextfast = fast.next #fast指针移到链表的空指针的位置beforeSlow.next = beforeSlow.next.next #执行删除操作return root1
4. 测试用例及测试结果
测试用例：
# Definition for singly-linked list.
class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def linkLength(self, root):length = 0r = rootwhile (r):length = length + 1r = r.nextreturn lengthdef removeNthFromEnd(self, head, n):if(head == None or head.next == None):return Noneif(self.linkLength(head) == n):return head.nextroot1 = headfast = headslow = headfor i in range(0, n): #fast指针向后移动n个元素fast = fast.nextwhile(fast):#快慢指针同时移动beforeSlow = slowslow = slow.nextfast = fast.next #fast指针移到链表的空指针的位置# print('beforeSlow',beforeSlow.val)# print('slow',slow.val)beforeSlow.next = beforeSlow.next.next #执行删除操作return root1def printLink(self,root):r = rootwhile(r):print(r.val)r = r.nextroot = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)root.next = n2
n2.next = n3
n3.next = n4
n4.next = n5s = Solution()
result = s.removeNthFromEnd(root,3)
# print(result)
s.printLink(result)
测试结果：
1
2
4
5
这篇关于Leetcode 19. 删除链表的倒数第N个节点 ----python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
