LeetCode 019 Remove Nth Node From End of List

LeetCode 019 Remove Nth Node From End of List

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

For 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.
Try to do this in one pass.

题目大意：

删除一个单链表末尾开始算起的第n个结点，然后返回该单链表。 例如：
输入: 1->2->3->4->5 其中n=2；
输出： 1->2->3->5;
n一定合法，只能遍历一次链表。

解题思路：

这是经典题。两指针法。距离为N的两指针，当前指针到末尾，后指针即是要删除的节点。头部插入fake节点，类似于mergeIntervals L56末尾插入一个空节点避免特别化处理。

1. 快指针从fake节点开始先走n步
2. 慢指针开始一起和快指针同步走，直到快指针到最后一个（next为空）
3. 此时慢指针是要删除指针的上一个，删除操作是可以的。

注意事项：

因为头指针也可能被删除，如只有一个节点的链表，n=1。删除操作在待删除节点的上一个节点上操作，所以引入假头节点prehead。

Java代码：

public ListNode removeNthFromEnd(ListNode head, int n) {
	ListNode prehead = new ListNode(-1);
	prehead.next = head;
	
	ListNode slow = prehead, fast = prehead;
	for(int i=0;i<n;i++)
		fast = fast.next;
	
	while(fast.next != null){
		fast = fast.next;
		slow = slow.next;
	}
	deleteNode(slow);
	return prehead.next;
}

public void deleteNode(ListNode p){
	p.next = p.next.next;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。