day10-删除链表的倒数第 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.com/problems/remove-nth-node-from-end-of-list
解题思路:
快慢指针:让快的指针先移动n位,然后快慢指针一起向后移动,这样的话当快指针移动到链表尾部时,慢指针刚好移动到链表的倒数第n位。
因为我们要删除倒数第n位,那么我们就需要将第n位上一位的next指向第n位的next,所以我们需要知道第n位的前一位(父节点)的位置,所以我们将慢指针设置为快指针移动n+1位后再同时向后移动,这样当快指针移动到链表末尾时,慢指针刚好指向倒数第n位的父节点,这时我们只需要nodeN.next = nodeN.next.next;就可以将第n位删除。
但是对于倒数第n位是链表头的话,它没有父节点,对于这种情况我们做特殊判断,我们只需要返回head.next就可以将头节点删除。
解题代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode nodeN = head;
ListNode next = head;
int i=1;
while(null!=next.next){
nodeN = i>n ? nodeN.next : nodeN;
next = next.next;
++i;//++i比i++效率更高,i++隐式的生成一个中间变量等于i+1,然后再将隐式变量的值赋值给i。
}
if(nodeN==head&&i-1!=n){
return head.next;
}else{
nodeN.next = nodeN.next.next;
}
return head;
}
}
执行效率: