leetcode 算法 19. 删除链表的倒数第N个节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//虚拟节点
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode k = sentinel;
while(n-- >0){
head = head.next;
}
while(null != head){
head = head.next;
k = k.next;
}
k.next = k.next.next;
return sentinel.next;
}
}
思路：
1、一次遍历，找到单链表的倒数K元素 =>
头结点正序遍历，找到正序第K个节点虚拟的哨兵节点，再跟正序节点按同步长向后遍历，抵达尾端 ，哨兵节点此时就是倒数K节点
2、单链表的遍历小技巧，增加头部哨兵节点
