标签：head ListNode val int next 链表 倒数第 节点 指针
leetcode 19. 删除链表的倒数第 N 个结点
题解1：通过链表长度获取[倒数第n个节点]位置
- 计算链表长度
- 找到[倒数第N个节点]的前一个节点
- 删除[倒数第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 tmp = head;
int len = 0;
while(tmp != null) {
tmp = tmp.next;
++ len;
}
if(n == len) return head.next;
int skip = len - n - 1; // 头节点跳到[倒数第n个节点]的前一个节点需要的步数
ListNode res = head;
while(skip -- != 0) {
head = head.next;
}
head.next = head.next.next; //删除[倒数第n个节点]
return res;
}
}
题解2：通过双指针确定[倒数第n个节点]位置
- 指针fir从链表头前一个位置，跳n步
- 指针fir和指针sec同时跳(len-n)步，则fir指针跳到链表尾，sec指针跳到[倒数第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 fir = new ListNode(0, head);
ListNode sec = fir;
// 第一个指针跳n下 至 第n个节点
int skip = n;
while(skip -- != 0) {
fir = fir.next;
}
if(fir.next == null) return head.next;
// 第一个指针跳len-n 下 至 尾节点
// 第二个指针同时跳 至 [倒数第n个节点]的前一个节点
while(fir.next != null) {
fir = fir.next;
sec = sec.next;
}
sec.next = sec.next.next;
return head;
}
}
标签：head,
ListNode,
val,
int,
next,
链表,
倒数第,
节点,
指针
From： https://www.cnblogs.com/Eve7Xu/p/17901669.html