当前位置 博文首页 > 学而不思则忘:删除链表的倒数第n个节点——NC.53
给定一个链表,删除链表的倒数第n个节点并返回链表的头指针
例如, 给出的链表为:1->2->3->4->5, n= 2.
删除了链表的倒数第n个节点之后,链表变为1->2->3->5.
备注: 题目保证n一定是有效的 请给出请给出时间复杂度为\ O(n) O(n)的算法
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 fast = head;
ListNode slow = head;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// 如果 n 的值等于链表长度 即删除的是第一个
if (fast == null) {
return head.next;
}
// 如果删除的不是第一个
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}
}
cs