leetcode算法题第19道，难度为medium，考察链表的基本操作。

Description

Given a linked list, remove the n-th node from the end of list and return its head.

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.

来源：leetcode 19 remove nth node from end of list

Solution

Approach 1 Reverse List

这道题是比较基础的一道题，我的思路是将链表翻转，这样就将题目转换为删去正数第n个元素。但是这种方法需要将链表翻转两次，所以从效率上来讲并不好，而且需要注意的边界条件还挺多，在这里仅作为参考思路。

ListNode* reverseList(ListNode* head) {
    ListNode* temp1 = head;
    ListNode* temp2 = head->next;
    while (temp2) {
	ListNode* t = temp2->next;
	temp2->next = temp1;
	temp1 = temp2;
	temp2 = t;
    }
    head->next = NULL;
    return temp1;
}

ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (head == NULL) {
	return NULL;
    }
    // 删去最后一个
    if (n==1) {
	if (head->next == NULL) {
	    return NULL;
	}
	ListNode* temp = head;
	while (temp->next) {
	    if (temp->next->next == NULL) {
		temp->next = NULL;
		break;
	    }
	    temp = temp->next;
	}
	return head;
    }
    // 翻转链表
    ListNode* temp1 = reverseList(head);
    // 找到需要删除的倒数第n个结点
    ListNode* temp3 = temp1;
    for (int i=2; i<n; ++i) {
	temp3 = temp3->next;
    }
    // temp3 此时是需要删除的节点的前一个节点
    // 如果删去的是头结点
    if (temp3->next == head) {
	temp3->next = NULL;
    }
    else {
	temp3->next = temp3->next->next;
    }
    // 关于内存释放问题，由于不知道内存是如何申请的（malloc，new），所以不能轻易释放
    // 此时节点删除完成
    return reverseList(temp1);
}

Approach 2 Two pass algorithm

这个解法是在leetcode的solution解析中看到的，解法的意图是将问题转化为删去正数第 l-n+1 个节点。其中 l 为链表的长度，这个是容易获得的。

下面是我按照这种思想使用C++进行编写的解法：

ListNode* removeNthFromEnd(ListNode* head, int n) {
    // 第一次遍历，得到链表长度
    int len = 0;
    ListNode* p1 = head;
    while (p1) {
	p1 = p1->next;
	++len;
    }

    // 删除正数第1个节点
    if (n == len) {
	ListNode* p = head->next;
	delete head;
	return p;
    }

    // 需要找到第 len - n 个节点（删除节点的前一个节点）
    ListNode* p2 = head;
    for (int i=0; i<len-n-1; ++i) {
	p2 = p2->next;
    }
    ListNode* p3 = p2->next;
    p2->next = p3->next;
    delete p3;
    p3 = nullptr;

    return head;
}

我在完成这个解法时，发现在删去正数第 l-n+1 个节点时，需要找到的实际上是正数第 l-n 个节点。这样，如果要删去正数第1个节点时，就需要对这个边界条件进行特殊处理。

使用一个 dummy 节点，将头节点包裹起来，就解决了之前的边界问题。 在遇到边界条件时，尝试将边界包裹起来，这样边界就转换为非边界了。 下面的实现代码截取自leetcode，使用java编写。

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;
}

这种算法的时间复杂为 O(l) ，第一次遍历求链表长度，第二次遍历找第 l-n 个节点，一共有 2L-n 次操作。空间复杂度为 O(1) ，没有使用额外的空间。

Approach 3 One pass algorithm

上面的解法能够优化为使用一轮循环。需要使用两个指针，第一个指针指向第 n+1 个节点，第二个指针指向第一个节点，这样两个指针就间隔 n 个节点了。同时将两个节点后移，在第一个指针到达尾部时，第二个指针所指的下一个节点就是需要删除的节点。
下面就是实现代码，截取自leetcode，使用java编写。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer
    // so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
	first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
	first = first.next;
	second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

这种算法的时间复杂为 O(l) ,它对链表进行了一次全遍历。空间复杂度为 O(1) ，没有使用额外的空间。

Extras

现在所有的方法都介绍到了，很明显，第三种方法的效率是最高的（操作次数最少）。这是在题目限定 n 一定有合理取值的情况下。如果 n 的取值有可能无效呢？这时就需要在每次指针操作时加以判断。再者，需要制定 n 取值无效时的策略，在取值无效时放弃本次删除操作，也可以删去与 n 距离最接近的节点。 n 的取值可能过小或过大。在 n 过小时（负数或0），可将 n 设定为1，这种情况对以上三种解法的影响是相同的。在 n 过大时，可以将 n 设定为 l ，这样第三种解法效率优势就会丢失，第一种和第二种解法受到的影响相对较小。