Q:
Given a linked list, remove the nth 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.
A:
（寫在最前面：兩種解法都特別要注意對dummy node和null node的處理）
一個指向（指針），跑兩遍鏈表：
public ListNode removeNthNode (ListNode node, int n){
ListNode dummy = new ListNode(0); //防止原鏈表第一個node被刪除
int length = 0;
int beforeTarget = 0; //定位到要刪除的node之前的node
dummy.next = head;
ListNode first = head;
while(first != null){
length ++;
first = first.next; //指向null為止
}
beforeTarget = length - n;
first = dummy;
while (beforeTarget > 0){
beforeTarget --;
first = first.next；//重新走一遍，走到要刪除的node之前的node停止
}
first.next = first.next.next;
return dummy.next;
}
.
如果鏈表里只有一個node：那么第一個while不執(zhí)行，計算beforeTarget時為負值，第二個while也不執(zhí)行，執(zhí)行first.next = first.next.next相當于是執(zhí)行dummy.next=dummy.next.next ( =null )。不管n是多少，這個鏈表都被刪干凈了。
.
第一個while里面計數(shù)起點是帶著dummy鏈表里的第二個點，因為起點指向dummy.next，但第二個while里面計數(shù)起點是從dummy開始的。
.
D -> 1 -> 2 -> 3 -> 4 -> 5 -> null
Length = 6，n = 2， 那么要刪的實際上是index值為5 = (L-n+1) 的node，所以，我們要找的前后兩個node分別為：(L-n) 和 (L-n+2)，只考慮(L-n)：beforeTarget = length - n;，因為(L-n+2)僅是個數(shù)學表達，它實際是通過.next.next來實現(xiàn)的。（一開始，這種數(shù)學表達不太直觀，畫出圖，按代碼邏輯多測幾組數(shù)據就好了。）
兩個指針，first和second，只跑了一遍鏈表：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head; //其實參數(shù)head除了這里，后面都沒用到
ListNode first = dummy;
ListNode second = dummy;
for (int i = 1; i <= n + 1; i++) {
first = first.next; //第一個指針先跑，從head node開始跑
}
while (first != null) {
first = first.next; //第一個指針跑到 null node 了，停！
second = second.next; //maintaing the same gap, gap是(n+1)個鏈條(->)
}
second.next = second.next.next; //指定的node被刪了
return dummy.next;
}
如果n=3，配個圖：
Notes：
由指針這件事，想到的Java和C++的區(qū)別:
.
- Java有回收機制，就不需要析構函數(shù)了（deconstructor）
- Java沒有指針
- Java不能多重繼承
- Java的"123"是對象，C++中是const char*
- Java不能操作符重載
ArrayList vs Linked-list（Dynamic data structure）
.
ArrayList包裝了一個Object[]，實例化的時候對應一個數(shù)組，訪問通過.get(index)，查找很方便，添加很麻煩，塞一個進去，后面的位置都得挪，ArrayList是順序存儲，而Linked-list是鏈式存儲，這兩者都是Dynamic的 (Array是Static的)。增刪數(shù)據LinkedList改節(jié)點的引用就好了，方便。但是要遍歷節(jié)點，速度慢。
(Lewis·Loftus Java Textbook page 619): A dynamic data structure is implemented using links. Using references as links between objects, we can create whatever type of structure is appropriate for the situation. If implemented carefully, the structure can be quite efficient to search and modify. Structures created this way are considered to be dynamic, because their size is determined dynamically, as they are used, and not by their declaration.
