java实现删除链表倒数第n个结点

实现删除链表倒数第n个结点，并且返回头结点。

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。

思路：使用两个结点，一个是p，一个是q。先让p向前走n步，然后p和q同时向前走，当p走到头的时候，q即是倒数n+1个结点了。另q.next=q.next.next，则删除了倒数第n个结点。
有两种特殊情况：
1.链表长度小于n，则返回原链表
2.链表长度为n，则返回head.next

代码实现：

/**
 * Definition for singly-linked list.--单链表的定义
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p = head;
        int i;
        for(i = 0; i < n; i++) //用于判断链表长度，同时让p先走n步
        {
            p = p.next;
            if(p == null)
                break;
        }
        if(i == n - 1 && p ==null) //链表长度为n时，头结点就是倒数第n个结点，删除头结点即可
            return head.next;
        if(i < n - 1 && p == null) //如果链表长度小于n，则不需要删除结点，返回原链表即可
            return head;
        ListNode q = head;
        while(p.next != null)
        {
            //这时让p和q同时向前走，直到链表遍历完成
            p = p.next;
            q = q.next;
        }
        q.next = q.next.next;
        return head;
    }
}