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

给你一个链表，删除链表的倒数第 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

package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/** * @Author Handsome * @Date 2022/8/6 20:17 * @Version 1.0 */
public class 删除链表的倒数第N个结点 {
    

    /** * Definition for singly-linked list. */
    public static class ListNode {
    
        int val;
        ListNode next;

        ListNode() {
    
        }

        ListNode(int val) {
    
            this.val = val;
        }

        ListNode(int val, ListNode next) {
    
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
    
        ListNode listNode = removeNthFromEnd(
                new ListNode(1,
                        new ListNode(2,
                                new ListNode(3,
                                        new ListNode(4,
                                                new ListNode(5))))), 2);
        List list = new ArrayList();
        while (listNode != null) {
    
            list.add(listNode.val);
            listNode = listNode.next;
        }
        System.out.println(list);
        // 输出结果 [1, 2, 3, 5]
    }

    /** * 双指针 * 复杂度分析: * 时间复杂度：O(L)，其中 L 是链表的长度。 * 空间复杂度：O(1)。 */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
    
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
    
            first = first.next;
        }
        while (first != null) {
    
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

我的学习论坛

HandsomeForum:用Java编写的学习论坛，打造我们自己的圈子！(http://huangjunjie.vip:66)