给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

  

static ListNode removeNthFromEnd(ListNode head,int n){
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode first=dummy;
        ListNode second=dummy;
        for(int i=0;i<=n;i++){
            first=first.next;
        }
        while (first!=null){
            first=first.next;
            second=second.next;
        }
        second.next=second.next.next;
        return dummy.next;
    }

View Code

思路：

  1.首先设置一个哑节点，哑节点的下一个节点就是原链表的第一个节点。

  2.第一个节点先走n+1步，走到原链表的第n个节点（由于前面加了个哑节点所有要走n+1步）。

  3.当第一个节点先走n+1步时，第二个节点开始走，此时2个间隔为n。

  4.当第一个节点走到为null时，第二个节点走到了倒数第n个节点的前一个节点。

  5.把第n个节点的前一个节点的下一个节点改为第n个节点的前一个节点的下一个节点的下一个节点。

  6.返回哑节点的下一个节点即可。