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.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if (head == null) return null; if (head.next == null) return null; ListNode p1, p2; int flag = 1; p1 = p2 = head; for (int i = 0; i < n; i++) { if (p2.next != null) p2 = p2.next; else flag = 0; } if (flag == 0) { head = head.next; } else { while (p2.next != null) { p1 = p1.next; p2 = p2.next; } p1.next = p1.next.next; } return head; } }我提交通过了，这里精髓就是利用双指针一次遍历就能做到，flag必不可少，因为删除的时候必须知道要删除的地方的上一个节点，这样一来，如果是删除头结点，那么会造成p2空指针异常，所以我们得设置一个flag标记一下。
提交成功之后又可以看别人优秀代码。 Approach #1 (Two pass algorithm)
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; int length = 0; ListNode first = head; while (first != null) { length++; first = first.next; } length -= n; first = dummy; while (length > 0) { length--; first = first.next; } first.next = first.next.next; return dummy.next; }这就是典型的遍历了两次链表才得到数据。
Approach #2 (One pass algorithm)
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode first = dummy; ListNode second = dummy; // Advances first pointer so that the gap between first and second is n nodes apart for (int i = 1; i <= n + 1; i++) { first = first.next; } // Move first to the end, maintaining the gap while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; return dummy.next; }思想跟我的是一样的，但是经过仔细推敲，他的这种处理头结点的办法比我那个可取，值得学习。
LeetCode官方指南
