[数据结构与算法] 力扣LeetCode第19题删除链表的倒数第N个结点

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 力扣LeetCode第19题删除链表的倒数第N个结点 -> 正文阅读

[数据结构与算法]力扣LeetCode第19题删除链表的倒数第N个结点

力扣LeetCode第19题删除链表的倒数第N个结点

题目：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

在这里插入图片描述

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

思路：
定义一个快指针一个慢指针，快指针先走N步，然后再同时走，快指针走到最后一个那么慢指针就是要删除的节点

代码：

/**
 * 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 fast = head, slow = head, pre = null;
      
        int i =0;
        while(fast != null) {
        //快指针先走N步
            if(i<n){
                fast = fast.next;
                i++;
                continue;
            }
            //pre指针始终指向慢指针的前一个结点，因为最后慢指针会指向倒数第N个结点
            pre = slow;
            slow = slow.next;
            fast = fast.next;
        }
        if(pre == null) {
            return head.next;
        }
        //让pre的下一个结点指向慢指针的下一个结点，那么就刚好把慢指针所在位置（倒数第N个结点删除了）
        pre.next = slow.next;
        return head;
    }
}