力扣19(java&python)-删除链表的倒数第 N 个结点（中等）

题目：

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

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

一、快慢指针

整体思路：设置两个指针，让前面的指针先走n步，之后前后的指针一起往后移动，直至前面的指针到尾结点。

• 先设置一个虚拟节点dummy指向原始头结点head,设前指针为start,后指针为end,两个指针均指向dummy；
• 前指针start先向后移动n步，此时start和end之间的距离为n；
• 之后start和end共同向后移动，当start到尾结点时，end正好在倒数第n个结点的前一个，正好可以删除倒数第n个结点，循环条件也就是start.next != null，删除后将end的下一个结点指向下下个结点；
• 删除后，返回dummy.next，不返回head的原因：可能head已经被删除了。

例如：

1.设置start、end和dummy

 

2.让start先向前移动n个

3.删除end的下一个,进行返回

注意：

1.设置虚拟结点的作用：删除一个结点需要找到它的前一个结点，所以如果对于需要删除头结点时，如果不设置一个虚拟结点指向原来的头结点，删除头结点就需要额外处理。这里设置虚拟结点就是把头结点当做普通结点（有前后结点）来看待。

2.最后返回的是dummy.next，而不是head?

head有可能就是需要被删除的结点，而虚拟结点是一直在链表的第一个，这样返回dummy.next就是链表头。

 

java代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     public ListNode removeNthFromEnd(ListNode head, int n) {
13         ListNode dummy = new ListNode(0,head);
14         ListNode start = dummy, end = dummy;
15         //让start先向前移动n个
16         while(n != 0){
17             start = start.next;
18             n--;
19         }
20         //start和end都向前移动
21         while(start.next != null){
22             start = start.next;
23             end = end.next;
24         }
25         //删除end的下一个
26         end.next = end.next.next;
27         return dummy.next;
28     }
29 }

 python3代码：

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, val=0, next=None):
 4 #         self.val = val
 5 #         self.next = next
 6 class Solution:
 7     def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
 8         # 设置虚拟头结点
 9         dummy = ListNode(0, head)
10         # 设定前后指针，均指向虚拟结点
11         start, end = dummy, dummy
12         # start先走n步
13         while n != 0:
14             start = start.next
15             n -= 1
16         # start和end一起向后移动
17         # 当start走到尾结点时，end刚好处于倒数第n-1个节点
18         while start.next:
19             start = start.next
20             end = end.next
21         # 删除第n个结点
22         end.next = end.next.next
23         return dummy.next

 二、栈

整体思路：设置一个栈，先将所有的结点弹入栈中，根据栈的特点后进先出，然后再弹出后n个结点，此时栈顶的结点就是待删除结点的前一个，然后将指针指向它的下下个结点，跳过待删除的结点，就将倒数第n个结点删除了。

• 先设置一个虚拟节点dummy指向原始头结点head,设一个当前结点也指向dummy，在设置一个栈；
• 将所有的结点弹入栈中；
• 弹出后n个结点；
• 然后弹出倒数第n+1结点（待删除结点的前驱结点），改变前驱结点的指针指向，使其指向下下个结点，这样就跳过了待删除的结点；
• 最后返回dummy.next。

java代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     public ListNode removeNthFromEnd(ListNode head, int n) {
13         ListNode dummy = new ListNode(0,head);
14         Deque<ListNode> stack = new ArrayDeque<>();
15         ListNode cur = dummy;
16         //将结点弹入栈中
17         while(cur != null){
18             stack.addLast(cur);
19             cur = cur.next;
20         }
21         //弹出后n个结点
22         while(n != 0){
23             stack.pollLast();
24             n--;
25         }
26         //弹出倒数第n+1个结点
27         ListNode pre = stack.peekLast();
28         //删除第n个结点
29         pre.next = pre.next.next;
30         return dummy.next;
31     }
32 }

 python3代码：

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, val=0, next=None):
 4 #         self.val = val
 5 #         self.next = next
 6 class Solution:
 7     def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
 8         # 设置虚拟头结点
 9         dummy = ListNode(0, head)
10         # 定义一个栈
11         stack = []
12         # 将当前结点指向dummy
13         cur = dummy
14         # 将结点弹入栈中
15         while cur:
16             stack.append(cur)
17             cur = cur.next
18         # 弹出后n个节点
19         for i in range(n):
20             stack.pop()
21         # 弹出栈顶结点（倒数第n个结点）
22         pre = stack[-1]
23         pre.next = pre.next.next
24 
25         return dummy.next

 

 小知识：

 python中想使用栈，其实就是使用列表list = [数据1，数据2，数据3，…]

1.入栈：

变量名.append(数据)：只能追加单个数据，对列表追加数据（相当于stack的push功能）

2.出栈：

pop():弹出列表中最后一个元素（就是stack的pop功能）

3.切片：

stack[-1]:从列表的最后一个开始数，截取一个数据。（为负就从后往前数）