JAVA练习297- 删除链表的倒数第 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]提示链表中结点的数目为sz1 sz 300 Node.val 1001 n sz进阶你能尝试使用一趟扫描实现吗来源19. 删除链表的倒数第 N 个结点 - 力扣LeetCode解题分析方法一数组1 sz 30因此我们可以定义一个长度为 31 的数组将每个节点依次存储进去并记录链表长度len那么只需要将 len - n - 1 的节点指针指向 len - n 1 的节点即可。注意长度不要越界了时间复杂度O(n)空间复杂度O(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[] nodes new ListNode[31]; ListNode node head; int index 0; while(node ! null) { nodes[index] node; node node.next; index; } if (n index) { return head.next; } nodes[index - n - 1].next nodes[index - n 1]; return head; } }方法二双指针定义两个指针 i 和 j指针 i 正常遍历指针 j 在 i 遍历 n 次后在遍历这样当 i 遍历完成时j 正好停在要删除的节点上进行移除即可。时间复杂度O(n)空间复杂度O(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) { ListNode i head, j head, pre null; int times 0; while(i ! null) { if (times n) { pre j; j j.next; } else { times; } i i.next; } if (j head) { return head.next; } pre.next j.next; return head; } }