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相當(dāng)于是執(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ù)學(xué)表達，它實際是通過.next.next來實現(xiàn)的抵恋。（一開始焕议，這種數(shù)學(xué)表達不太直觀，畫出圖弧关，按代碼邏輯多測幾組數(shù)據(jù)就好了盅安。）
兩個指針，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有回收機制墙歪，就不需要析構(gòu)函數(shù)了（deconstructor）
- Java沒有指針
- Java不能多重繼承
- Java的"123"是對象，C++中是const char*
- Java不能操作符重載
ArrayList vs Linked-list（Dynamic data structure）
.
ArrayList包裝了一個Object[]贝奇，實例化的時候?qū)?yīng)一個數(shù)組虹菲，訪問通過.get(index)，查找很方便弃秆，添加很麻煩届惋，塞一個進去，后面的位置都得挪菠赚，ArrayList是順序存儲脑豹，而Linked-list是鏈?zhǔn)酱鎯Γ@兩者都是Dynamic的 (Array是Static的)衡查。增刪數(shù)據(jù)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.
