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

题目

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

解答：

直觉解答：

两次遍历算法：第一遍先遍历整个链表确定链表长度L，第二遍遍历到（L-n）的位置，跳过倒数第n个节点，连接到倒数第n-1个节点，返回头指针。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
    	// 用来保存头节点，如果被删除的节点非头节点，直接返回该节点
        ListNode oldhead = head;
        int length = 0;
        // 遍历链表以记录链表长度
        while(head.next != null)
        {
            length++;
            head = head.next;
        }
        length++;
        // 将head节点指向头节点
        head = oldhead;
        // 删除非头节点时
        if(n != length)
        {
            for(int i = 0;i<(length - n)-1;i++)
            {
                head = head.next;
            }
            head.next = head.next.next;
        }
        // 否则
        else
        {
            oldhead = head.next;
        }
        return oldhead;
    }
}

这个版本写的并不好，逻辑不清晰，因为设定链表从0开始计数所以表示的不太容易理解。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int length  = 0;
    ListNode first = head;
    while (first != null) {
        length++;
        first = first.next;
    }
    length -= n;
    first = dummy;
    while (length > 0) {
        length--;
        first = first.next;
    }
    first.next = first.next.next;
    return dummy.next;
}

一个对应的Java实现版本。

官方题解：

1. 两次遍历方法：如上。

2. 一次遍历法：上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。

   /**
    * Definition for singly-linked list.
    * public class ListNode {
    *     public int val;
    *     public ListNode next;
    *     public ListNode(int x) { val = x; }
    * }
    */
   public class Solution {
       public ListNode RemoveNthFromEnd(ListNode head, int n) {
       ListNode dummy = new ListNode(0);
       dummy.next = head;
       ListNode first = dummy;
       ListNode second = dummy;
       for(int i = 1;i<=n;i++)
       {
           first = first.next;
       }
       while(first != null)
       {
           first = first.next;
           second = second.next;
       }
       second.next = second.next.next;
       return dummy.next;
       }
   }