Remove Nth Node From End of List

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.

java code: 注意题目要求在一趟内完成，也就是只遍历一次，则开两个引用相隔n个结点，注意n为链表长度时的特殊情况：

/** 
 * 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) {  
        // Note: The Solution object is instantiated only once and is reused by each test case.  
        if(head == null)  
            return null;  
        ListNode p = head;  
        ListNode q = head;  
        for(int i = 0; i < n; i++)  
        {  
            q = q.next;  
        }  
        if(q == null)  
        {  
            head = head.next;  
            p = null;  
            return head;  
        }  
        while(q.next != null)  
        {  
            p = p.next;  
            q = q.next;  
        }  
        ListNode tmp = p.next.next;  
        p.next = tmp;  
        return head;  
          
    }  
}

完整的测试代码：开发环境： win7(64) + eclipse

import java.util.ArrayList;  
class ListNode  
{  
    int val;  
    ListNode next;  
    ListNode(int x)  
    {  
        val = x;  
        next = null;  
    }  
}  
  
public class Helloworld {  
  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
        ListNode head = new ListNode(1);  
        ListNode cur = head;  
        for(int i = 0; i < 4; i++)  
        {  
              
            ListNode tmp = new ListNode(i+2);  
            cur.next = tmp;  
            cur = tmp;  
        }  
        cur = remove(head,2);  
          
        for(;cur != null;)  
        {  
            System.out.println(cur.val);  
            cur = cur.next;  
        }  
      
          
    }  
    public static ListNode remove(ListNode head, int n)  
    {  
        if(head == null)  
                return null;  
        ListNode p = head, q = head;  
        for(int i = 0; i < n; i++)  
        {  
            q = q.next;  
        }  
        while(q.next != null)  
        {  
            p = p.next;  
            q = q.next;  
        }  
        ListNode tmp = p.next.next;  
        p.next = tmp;  
        return head;  
    }  
  
}

补充：软件开发 , Java ,