您的位置 首页 java

LeetCode每日一题,删除链表的倒数第N个结点

题目

删除链表的倒数第 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!!!

文章来源:智云一二三科技

文章标题:LeetCode每日一题,删除链表的倒数第N个结点

文章地址:https://www.zhihuclub.com/196394.shtml

关于作者: 智云科技

热门文章

网站地图