题目
删除链表的倒数第 N 个结点
CODE -cn.com/problems/remove-nth-node-from-end-of-list/
描述
难度: 中等
给你一个 链表 ,删除链表的倒数第 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
Solution
双指针解法
解题思路
很幸运,几乎一遍成功,最近准备多刷刷双指针的题,做着觉得挺有意思的,废话不多说,今天这个题的解法就是标准的双指针类型
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点
首先给定一个链表,链表特性不过多解释,每个结点都有对应的next结点指向下一个结点,给定一个数字 N ,删除倒数第 N 个结点
- 首先指定一个 首指针 ,因为是链表,删除N结点只需要改动前后指针的指向即可,首指针基本不用动(除了N为当前链表长度,即删除首结点),最后可以直接返回 首指针 即可
- 指定 N指针 ,表示倒数N结点的位置
- 指定 cur指针 ,表示当前遍历链表的位置,当cur指针的next为 null 时,说明已经遍历到链表尾部
- 倒数 N 个结点,我们可以先从首结点开始计算,计算出N距离, N指针 指向N距离的头部, cur指针 指向N距离的尾部
- 依次移动 cur指针 , N指针 ,直到cur指针的next为null,停止遍历
- 特殊处理,当 n 的值 == 链表的长度,即删除第一个结点,直接返回 head.next 即可
以首结点位置,计算N的距离,N指针指向N距离的头部,cur指针指向N距离的尾部
移动cur指针,只要cur指针的next不为null,则同时移动N指针以及cur指针
cur指针的next为null,即遍历到链表的尾部,当前N指针对应的结点就是倒数N的结点
CODE
/**
* 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; }
if(head.next ==null){
return null;
}
* }
*/ class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//首指针
ListNode res = head;
//cur指针,当前链表遍历结点
ListNode cur = head;
//N指针,指向倒数N的结点
ListNode nNode = head;
//PREN指针,指向倒数N的前一个结点,用以删除N结点,PREN.next = n.next
ListNode preNNode = head;
//初始化,先使cur指针,指向N距离的尾部
for(int i =1;i<n ; i++){
cur = cur.next;
}
//特殊处理,n的值 == 链表的长度,即删除第一个结点,直接返回head.next即可
if(cur.next==null){
return res.next;
}
//当前遍历是否到尾部
while(cur.next!=null){
//当前结点赋值给preN
preNNode = nNode;
//N指针后移
nNode = nNode.next;
//cur指针后移
cur = cur.next;
}
//删除N结点
preNNode.next = nNode.next;
return res;
}
}
复杂度
- 时间复杂度: O(N) ,N为链表长度
- 空间复杂度: O(1) ,除了链表本身,没有其他内存空间开销
结果
- 执行用时: 0 ms, 在所有 Java 提交中击败了 100.00 %的用户
- 内存消耗: 36.1 MB, 在所有 Java 提交中击败了 96.98 %的用户
LeetCode名句
LBWNB!!!