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不执行，计算beforeTarget时为负值，第二个while也不执行，执行first.next = first.next.next相当于是执行dummy.next=dummy.next.next ( =null )。不管n是多少，这个链表都被删干净了。
.
第一个while里面计数起点是带着dummy链表里的第二个点，因为起点指向dummy.next，但第二个while里面计数起点是从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)仅是个数学表达，它实际是通过.next.next来实现的。（一开始，这种数学表达不太直观，画出图，按代码逻辑多测几组数据就好了。）

两个指针，first和second，只跑了一遍链表：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head; //其实参数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++的区别:

.

• Java有回收机制，就不需要析构函数了（deconstructor）
• Java没有指针
• Java不能多重继承
• Java的"123"是对象，C++中是const char*
• Java不能操作符重载

ArrayList vs Linked-list（Dynamic data structure）

.
ArrayList包装了一个Object[]，实例化的时候对应一个数组，访问通过.get(index)，查找很方便，添加很麻烦，塞一个进去，后面的位置都得挪，ArrayList是顺序存储，而Linked-list是链式存储，这两者都是Dynamic的 (Array是Static的)。增删数据LinkedList改节点的引用就好了，方便。但是要遍历节点，速度慢。

(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.