首页 > 代码库 > LeetCode --- 19. Remove Nth Node From End of List
LeetCode --- 19. Remove Nth Node From End of List
题目链接：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个元素（n总是有效的），不过要求遍历1次链表。
这道题的思路比较简单，采用快慢指针，先用快指针f从头后移n次，这样f就比慢指针s快了n个节点，然后f和s同时后移，直到f到达链表尾部，此时，s即为要删除的节点。
不过在处理链表的时候，有个小技巧，就是先给链表加头，这样就可以把链表的head节点也当成普通节点处理。而在加了头之后，就需要判断f的next是否到达链表尾部，当f的next到达链表尾部是，s的next刚好为要删除的节点，这样也方便删除节点。
时间复杂度：O(n)
空间复杂度：O(1)
1 class Solution
2 {
3 public:
4 ListNode *removeNthFromEnd(ListNode *head, int n)
5 {
6 ListNode *h = new ListNode(0);
7 h -> next = head;
8
9 ListNode *f = h, *s = h;
10 while(n --)
11 f = f -> next;
12 while(f -> next != NULL)
13 {
14 f = f -> next;
15 s = s -> next;
16 }
17 s -> next = s -> next -> next;
18
19 return h -> next;
20 }
21 };说明一下，好多的链表题目都需要用采用双指针（或者说快慢指针）处理，像是判断链表是否有环、找链表中出现环的位置、找两链表的交点等等。。。
转载请说明出处：LeetCode --- 19. Remove Nth Node From End of List
LeetCode --- 19. Remove Nth Node From End of List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。