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.
这道题要注意的Corner Case是：如果n比这个LinkedList的size大，那么就需要直接返回Head，如果相等，就把head删掉，返回head.next；基本做的方法呢，还是Runner Technique. 由于有可能head会被删掉，所以最好还是使用一个dummy node，dummy.next = head。
第25行如何判断 n > listSize要想清楚，因为如果runner移动到末尾runner.next == null时，此时 i 刚好是listSize，若n>i, 则n > listSize
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 public ListNode removeNthFromEnd(ListNode head, int n) { 14 if (head == null) return null; 15 if (n <= 0) return head; 16 ListNode dummy = new ListNode(-1); 17 dummy.next = head; 18 ListNode runner = dummy; 19 ListNode walker = dummy; 20 int i = 0; 21 while (i<n && runner.next!=null) { 22 i++; 23 runner = runner.next; 24 } 25 if (i < n) return head; // n > list's size 26 while (runner.next != null) { 27 runner = runner.next; 28 walker = walker.next; 29 } 30 walker.next = walker.next.next; 31 return dummy.next; 32 } 33 }