[数据结构与算法] LeetCode19. 删除链表的倒数第 N 个结点

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

-> 数据结构与算法 -> LeetCode19. 删除链表的倒数第 N 个结点 -> 正文阅读

[数据结构与算法]LeetCode19. 删除链表的倒数第 N 个结点

思路

思路就是找到倒数第n个节点的前一个接点，让其指向其下下个节点即可。

用双指针，一个执行头结点，一个执行第n个节点，让两个节点一起移动，当快节点到达末尾时，慢节点指向的位置就是倒数第n个节点的位置，为了找到倒数第n+1个位置，就让慢节点从虚节点开始遍历。

代码

/**
 * 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) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode dummyNode = new ListNode(-1,head);
        ListNode slow = dummyNode;
        ListNode fast = head;
        for(int i = 0;i<n;i++){
            fast = fast.next;
        }
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummyNode.next;
    }
}