牛客题霸每日一题NC53题解Java8语言描述
题目描述
给定一个链表，删除链表的倒数第n个节点并返回链表的头指针
例如，
例如，
给出的链表为:1->2->3->4->5, n= 2. 删除了链表的倒数第n个节点之后,链表变为1->2->3->5.备注：
题目保证n一定是有效的
请给出请给出时间复杂度为\ O(n) O(n)的算法
请给出请给出时间复杂度为\ O(n) O(n)的算法
解题思路
使用双指针找链表倒数第n+1个节点，并删除该节点后一节点。
使用伪头指针哨兵，统一边界情况。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
ListNode dummyHead = new ListNode(0), fast = dummyHead, slow = dummyHead;
dummyHead.next = head;
for(int i = 0; i < n; ++i){
fast = fast.next;
}
while(fast != null && fast.next != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
}
