目录
19. 删除链表的倒数第 N 个结点
方法1 通过链表长度直接删除
方法2 递归加入哨兵节点
ListNode
方法3 快慢指针法
苦难，区区挫折罢了，而我必定站在幸福的塔尖
—— 24.9.22
19. 删除链表的倒数第 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
方法1 通过链表长度直接删除
计算链表长度，通过链表长度倒数找到被删除的元素，直接删除该元素
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);int num = 0;while (head != null) {num++;head = head.next;}ListNode cur = dummy;for (int i = 0; i < num - n ; i++) {cur = cur.next;}cur.next = cur.next.next;ListNode ans = dummy.next;return ans;}
}
方法2 递归加入哨兵节点
递归加入哨兵节点
因为加入了哨兵节点，所以这里要修改ListNode类的遍历方式，从哨兵节点的下一个节点开始遍历，在ListNode类中加入一个哨兵节点，指向头节点的下一个节点
ListNode
public class ListNode {public int val;public ListNode next;public ListNode(int val, ListNode next) {this.val = val;this.next = next;}public static ListNode of(int...numbers) {ListNode head = new ListNode(0, null);ListNode current = head;for (int number : numbers) {current.next = new ListNode(number, null);current = current.next;}return head;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder(64);sb.append("[");ListNode p = this.next;while (p != null) {sb.append(p.val);if (p.next != null) {sb.append(",");}p = p.next;}sb.append("]");return sb.toString();}
}
ppublic class LeetCode203RemoveListData {public static ListNode removeElements1(ListNode head, int val) {ListNode s = new ListNode(-1,head);ListNode p1 = s;ListNode p2 = s.next;while (p2 != null) {if (p2.val == val) {p1.next = p2.next;p2 = p2.next;}else {p1 = p2;p2 = p2.next;}}return s.next;}public ListNode removeElements2(ListNode head, int val) {if (head == null) {return head;}head.next = removeElements2(head.next, val);return head.val == val ? head.next : head;}
}
方法3 快慢指针法
定义两个指针，使两个指针中间保持倒数节点+1的位置，是两个指针同时遍历，当快指针遍历到null时，慢指针的位置即是倒数指针的位置
/*** 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 s = new ListNode(-1, head);ListNode p1 = s;ListNode p2 = s;// 倒数n位，移动到倒数n+1的位置for (int i = 0; i < n + 1; i++) {p2 = p2.next;}while(p2 != null){p1 = p1.next;p2 = p2.next;}p1.next = p1.next.next;return s.next;}
}
