成都广告设计制作公司搜索引擎优化论文

【力扣】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]

提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

题解

方法一：两次遍历

• 先遍历一次链表，求出链表的总长度。
• 根据总长度 length 的值-n，就算出需要再遍历多少个节点，找到要删除的节点的前一个节点 x。
• 将 x 节点的 next 指针指向下下一个节点就可以删除节点了。

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 class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if (head == null || n <= 0) {return head;}//增加一个特殊节点，方便边界处理ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode cur = dummyNode;//第一次遍历，计算链表总长度int length = 0;while (cur.next != null) {cur = cur.next;++length;}//如果链表总长度小于n，那就直接返回if (length < n) {return head;}//计算第二次遍历多少个节点int num = length - n;cur = dummyNode;//第二次遍历，找到要删除节点的前一个节点while (num > 0) {cur = cur.next;--num;}//删除节点，并返回cur.next = cur.next.next;return dummyNode.next;}
}

方法二：一次遍历（快慢指针）

需要两个指针 slow 和 fast。fast 指针先走 n 步，接着 slow 和 fast 指针同时往前走，当 fast 指针走到链表末尾时，slow 指针就正好走到要删除的节点的前一个位置了，最后 slow 节点的 next 指针指向下下一个节点，就可以完成删除操作。

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 class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//增加一个特殊节点方便边界判断ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode slow = dummyNode;ListNode fast = dummyNode;//第一个循环，fast 指针先往前走n步while (n > 0 && fast != null) {fast = fast.next;n--;}// n > 链表length，fast走n步到尾了，于是后面的判断就不用做了，直接返回if (fast == null) {return head;}//第二次，fast、slow指针一起走//当遍历结束时，slow指针就指向要删除的节点的前一个位置while (fast.next != null) {slow = slow.next;fast = fast.next;}//删除节点并返回slow.next = slow.next.next;return dummyNode.next;}
}