LeetCode 笔记系列四 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.

就是让你删除单链表倒数第n个节点，同时希望能只遍历一次。

解法一：如果不遍历完所有节点，怎么知道倒数第n个在哪里呢？但是遍历完成以后，删除不是又需要遍历么？不过删除一个node实际上只需要一个pre node就行了。于是，考虑使用一个HashMap保存遍历过的节点，实现删除。

 1 public ListNode removeNthFromEnd(ListNode head, int n) {
 2         // Start typing your Java solution below
 3         // DO NOT write main() function
 4         if(head == null) return null;
 5         HashMap<Integer, ListNode> map = new HashMap<Integer, ListNode>();
 6         int i = 0;
 7         ListNode p = head;
 8         while(p != null){
 9             map.put(++i, p);
10             p = p.next;
11         }
12         ListNode pre = map.get(i - n);//i - n is the node that right BEFORE the to-be-deleted node.
13         if(pre != null){
14             ListNode deleted = pre.next;
15             if(deleted != null)
16                 pre.next = deleted.next;
17         }else {//if pre is null, means we are deleting head
18             head = head.next;
19         }
20         return head;
21     }

HashSet deletion

感觉每次做题，如果用到了额外的数据结构或者空间，都有一种开挂的感觉。能不能不显式使用额外的空间或者数据结构呢？想到最近看了Algorithm 4th edtion关于递归删除BST的方法，有一些启发。

解法二：我们尝试使用递归来解。

 1 public ListNode removeNthFromEnd2(ListNode head, int n) {
 2         if(head == null) return null;
 3         int[] counter = new int[]{0};
 4         return removeNthFromEnd2(head,n,counter);
 5     }
 6     
 7     private static ListNode removeNthFromEnd2(ListNode head, int n, int[] counter){
 8         if(head.next == null){// we reached tail
 9             counter[0] = 1;
10         }else {
11             head.next = removeNthFromEnd2(head.next, n, counter);
12             counter[0]++;//we increment this counter to record when we back from the recursive, namely back from the last node
13         }
14         if(counter[0] == n){//oh, this is nth node backward, we just RETURN THE NEXT NODE.
15             return head.next;
16         }else return head;//otherwise return whatever we received
17     }

recursive deletion

是不是看上去很简洁？同样的，我们还是需要遍历完所有节点。但是递归的好处是每次返回的都是“backward"，通过这个特点，我们使用一个counter变量，在递归返回的时候，记录返回经过的节点（Java不如C#，没有ref参数，所以只能用一个数组记录这个counter变量以达到引用的效果）。这样当counter到打n的时候，我们知道，哦，好啦这个当前节点就是我们要删除的节点咯。所以，instead of直接返回head节点，我们返回删除节点的next，这样，在递归调用再次返回的时候，pre的next就指向了删除节点的next咯。

好吧，承认实际上这也是遍历了两次链表。。。：<

解法三：为了减少遍历，我们还可以用两个指针slow和fast，fast先走n步。then，slow和fast共同进步直到fast走到尾巴。Code在这里。