LeetCode每日一题，删除链表的倒数第 N 个结点|刷题打卡-一一网

题目

删除链表的倒数第 N 个结点

leetcode-cn.com/problems/re…

公众号《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注

java编程手记

描述

难度：中等

给你一个链表，删除链表的倒数第 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;
    }
}
复制代码