其他
【LeetCode】（No.019）删除链表的倒数第N个节点
点击上方“Ahab杂货铺”，选择“置顶公众号”
技术分享第一时间送达！
NO.19 删除链表的倒数第N个节点
一、写在前面
刷题模块的初衷是恶补数据结构和算法，不管自己的公众号怎样变化，刷题这个模块一定会保留下去，期待自己能成为offer收割机。LeetCode
第十八题传输门：【LeetCode】（No.018） 四数之和天给大家分享的是LeetCode 第十九题：删除链表的倒数第N个节点。
前十题汇总：【LeetCode】打卡记录（NO.1-10）为面试而生，期待你的加入。
二、今日题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表:1->2->3->4->5,和 n = 2. 当删除了倒数第二个节点后，链表变为
1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
三、 分析
这个题目的大意就是删除一个单链表中的倒数第N个结点，这个题目还是比较简单的下面是具体的解题思路。
两次遍历单链表，首先获得单链表中的结点个数count，然后从前往后找到第count-N+1个结点，即我们要删除的结点，删除即可。一次遍历链表，用两个指针p,q分别指向头结点，然后先将其中一个指针p向后移动N个位置，再将p,q同时往后移动，当指针p移动到末尾时，q指针指向的结点即为我们要删除的结点。
四、解题
第一种解题：
1# Definition for singly-linked list.
2# class ListNode:
3# def __init__(self, x):
4# self.val = x
5# self.next = None
6
7class Solution:
8 def removeNthFromEnd(self, head, n):
9 temp = head
10 count = 0
11 while temp!=None:
12 temp = temp.next
13 count += 1
14 temp = head
15 index = 0
16 if count==n:
17 return head.next
18 else:
19 while index!=(count-n-1):
20 temp = temp.next
21 index += 1
22 temp.next = temp.next.next
23 return head
第二种解题：
1# Definition for singly-linked list.
2# class ListNode:
3# def __init__(self, x):
4# self.val = x
5# self.next = None
6
7class Solution:
8 def removeNthFromEnd(self, head, n):
9 p = head
10 q = head
11 index = 0
12 while index!= n:
13 p = p.next
14 index += 1
15 if p==None:
16 return head.next
17 while p.next!= None:
18 p = p.next
19 q = q.next
20 q.next = q.next.next
21 return head
往期推荐阅读：
欢迎您的点赞和分享
▲长按关注此公众号