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个元素，不过题目要求一次遍历实现。
这个问题的最直接的想法就是两次遍历，首先先遍历一次得到len，然后从正面遍历到len+1-k个元素，并删除。
其实使用栈也是不错的做法
不过题目要求是一次遍历，有什么解决办法呢? 看了网上的解决办法，于是乎才明白可以使用长度为n+1的子链表来解决，这个类似移动窗口算法。需要注意的是：使用n+1的子链表就是n个间隔n+1个元素，这样是为了便于删除元素；同时要注意处理删除元素就是head结点的特殊情况的处理。
代码如下：
/*class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }*/ /* * 题目说保证n是有效的，这个意思就是说n<len * 同时题目要求一次遍历解决问题 * * 本题的思想就是利用一个长度为n+1的子链表，，有点类似移动窗口， * 通过移动子链表到最后一个结点 * 从而来确定导数第n个元素是谁，注意这里使用n+1的子链表就是为了方便删除元素， * 这个很容易理解 * * */ public class Solution { /* * 这个是两次遍历的解决办法 * */ public ListNode removeNthFromEnd(ListNode head, int n) { if(head==null || n<=0) return head; ListNode iter=head; int count=0; while(iter!=null) { iter=iter.next; count++; } if(count==n) head=head.next; else { int target=count+1-n; iter=head; ListNode fa=head; for(int i=1;i<=target;i++) { if(i==target) { fa.next=iter.next; break; }else { fa=iter; iter=iter.next; } } } return head; } /* * 使用长度为n+1的子链表实现，有点类似移动窗口 * */ public ListNode removeNthFromEnd11(ListNode head, int n) { if(head==null || n<=0) return head; ListNode start=head,end=head; /* * 因为n是有效的，所以这个循环不会报错，最多end为null走到了最后 * 这里是循环次数为n的for循环，表示的子链表的间隔是n，也就是说元素是n+1个 * */ for(int i=0;i<n;i++) end=end.next; if(end==null) head=head.next; else { while(end.next!=null) { start=start.next; end=end.next; } //start 到 end 是n个间隔，就是有n+1个点，所以start.next才是我们要删除的结点 start.next=start.next.next; } return head; } }下面是C++的一次遍历的做法，就是一个移动窗口问题。
代码如下：
#include <iostream> #include<stdio.h> using namespace std; /* struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { if (head == NULL || n <= 0) return head; ListNode* start = head; ListNode* end = head; for (int i = 0; i < n; i++) end = end->next; if (end == NULL) head = head->next; else { while (end->next != NULL) { start = start->next; end = end->next; } start->next = start->next->next; } return head; } };