Java教程

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

本文主要是介绍力扣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]:从列表的最后一个开始数,截取一个数据。(为负就从后往前数)

这篇关于力扣19(java&python)-删除链表的倒数第 N 个结点(中等)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!