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.
Solution:
快慢指针。快的比慢的快n个位置，这样快的指针指到末尾的时候，慢的指针刚好距离list末尾n个位置。
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 ListNode dummy=new ListNode(0); 15 dummy.next=head; 16 17 ListNode fast=dummy, slow=dummy; 18 while(fast!=null&&n>0){ 19 fast=fast.next; 20 n--; 21 } 22 while(fast.next!=null){ 23 fast=fast.next; 24 slow=slow.next; 25 } 26 slow.next=slow.next.next; 27 return dummy.next; 28 } 29 }
第一次提交的时候报错，问题在：
slow.next=slow.next.next;
我写成了
slow.next=fast;
当时由于自己只在草稿纸上画了下n=2的例子，而忘记了n的含义：nth node from the end of list.
[Leetcode] Remove Nth Node From End of List
原文：http://www.cnblogs.com/Phoebe815/p/4039345.html