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->NULL,
n =2; 这时，要删除的就是头节点。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // Start typing your Java solution below // DO NOT write main() function ListNode p = head; int totalNum = 0; while(p != null){ totalNum ++; p = p.next; } if(totalNum == n){ head = head.next; return head; } ListNode p1 = head; for(int i = 0; i < (totalNum - n - 1); i ++){ p1 = p1.next; } ListNode p2 = p1.next; if(p2 != null) p1.next = p2.next; else p1.next = null; return head; } }
ref: http://www.cnblogs.com/feiling/p/3189337.html
http://fisherlei.blogspot.com/2012/12/leetcode-remove-nth-node-from-end-of.html
[Leetcode]-- Remove Nth Node From End of List
原文：http://www.cnblogs.com/RazerLu/p/3537897.html