题目地址

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

https://labuladong.gitee.io/plugin-v3/?qno=19&target=gitee&labuladong 题解

LeetCode原题
https://leetcode-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

 

进阶：你能尝试使用一趟扫描实现吗？

前置知识

LeetCode官方题解

代码随想录题解https://programmercarl.com/0019.删除链表的倒数第N个节点.html#其他语言版本

思路

关键点

• 解法1快慢指针：双指针的一种，快指针先利用for循环先走，比慢指针多走n+1，然后利用for循环同时移动快慢指针，直到快指针移到链表末尾，此时慢指针指向需要删除的倒数第n个节点的前一个节点，慢指针指向下下个节点
• 解法2：先算出传入的链表长度length，用length减去倒数前n个节点，length-n+1即表示待删除的倒数第n个节点,利用for循环遍历指针到待删除节点的前一个节点。然后同上。

代码

• 语言支持：Java

Java 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; }
 * }
 */
class Solution {
    //解法一：双指针之快慢指针
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        ListNode fast = dummy;
        ListNode slow = dummy;
        for(int i = 0;i<=n;i++){
            fast = fast.next;
        }
        while(fast!= null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
    //解法二：利用for循环来遍历到需要删除的前一个节点。
public ListNode removeNthFromEnd(ListNode head,int n){
    ListNode dummy = new ListNode(0,head);
    ListNode cur = dummy;
    for(int i = 0; i<getLength(head)-n;i++){
            cur = cur.next;
    } 
    cur.next = cur.next.next; 
    return dummy.next;
}
 public int getLength(ListNode head){
     int length =0 ;
    while(head!=null){
        length ++;
        head = head.next;
    }
    return length;
}
}