导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-19.Remove Nth Node From End of List

题目

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

翻译

给出一个链表,去除从后向前第n个节点,返回链表头。
例如,给出链表:1->2->3->4->5,n = 2。在去除从后向前第2个节点后,链表变为1->2->3->5。
注意:
给出的n总是合法的。
尝试一趟完成操作。

设立快慢指针,快指针先走n步,然后快慢指针同时走,当快指针的后继为空时停止,让慢指针的后继指向其后继的后继,返回头结点。
需要注意的是,当快指针走n步后,如果指向空,则要删除的是头结点,直接返回head.next:

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode slow = head, fast = head;
while (n-- > 0)
fast = fast.next;
if (fast == null)
return head.next;
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}

参考:
http://blog.csdn.net/yao_wust/article/details/41242805