当前位置：网站首页>＃yyds干货盘点＃面试必刷TOP101：删除链表的倒数第n个节点

＃yyds干货盘点＃面试必刷TOP101：删除链表的倒数第n个节点

2022-08-02 15:33:00 【51CTO】

1.简述：

描述

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针例如，

给出的链表为: , .删除了链表的倒数第个节点之后,链表变为.

数据范围：链表长度，链表中任意节点的值满足

要求：空间复杂度，时间复杂度备注：

题目保证一定是有效的

示例1

输入：

返回值：

2.代码实现：

       
       import java.util.*;
       
public class Solution {
       
    public ListNode removeNthFromEnd (ListNode head, int n) {
       
        //添加表头
       
        ListNode res = new ListNode(-1); 
       
        res.next = head;
       
        //当前节点
       
        ListNode cur = head; 
       
        //前序节点
       
        ListNode pre = res; 
       
        ListNode fast = head;
       
        //快指针先行n步
       
        while(n != 0){ 
       
            fast = fast.next;
       
            n--;
       
        }
       
        //快慢指针同步，快指针到达末尾，慢指针就到了倒数第n个位置
       
        while(fast != null){
       
            fast = fast.next;
       
            pre = cur;
       
            cur = cur.next;
       
        }
       
        //删除该位置的节点
       
        pre.next = cur.next; 
       
        //返回去掉头
       
        return res.next; 
       
    }
       
}
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.