题目:
给你一个链表,删除链表的倒数第 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]
提示:
进阶:你能尝试使用一趟扫描实现吗?
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
一、快慢指针
整体思路:设置两个指针,让前面的指针先走n步,之后前后的指针一起往后移动,直至前面的指针到尾结点。
例如:
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个结点删除了。
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]:从列表的最后一个开始数,截取一个数据。(为负就从后往前数)