删除链表的倒数第N个节点

 

cur, pre 指针保持n个节点的距离的距离。    pre 最终指向的是要删除节点的前一个节点， cur 最终指向的是 null, 或者最后一个节点。

/**
 * 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 cur,pre;
        cur = pre = head;
        
　　　　　// cur 提前走n 个节点。 但是cur 可能会跑到链表末尾。
        for( int i=1; i<=n; ++i )
            cur = cur.next;
        
        if( cur == null ){    // 这个判断狠重要。
             return head.next;
        }
        
        while( cur.next != null ){
            cur = cur.next;
            pre = pre.next;
        }
        
        ListNode tmp = pre.next;
        pre.next = tmp.next;
        
        return head;
        
    }
}