Paste_Image.png

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n <= 0)
            return null;
        int count = 0;
        boolean isN = false;
        ListNode temp = head;
        ListNode tempN = head;
        while(temp != null) {
            if (temp.next == null)
                break;
            if (isN)
                tempN = tempN.next;
            temp = temp.next;
            count++;
            if (count == n)
                isN = true;
        }
        if (tempN.next == null)
            head = null;
        else if (count == n - 1)
            head = head.next;
        else
            tempN.next = tempN.next.next;
        return head;
    }
}

My test result:

Paste_Image.png

这次作业比较简单，但如果按照他所说的， one pass就做出结果，就得动点脑子了。
方法就是 two pointer。 当前一个指针和链表相距 n 时，后一个指针就可以开始跟着前一个指针一个个得向前移动。最后前一个指针到头时，后一个指针就是该移除节点的位置。
当然会有一些细节需要考虑。
比如，链表只有一个节点，而 n = 1
链表有两个节点，而 n = 2
这几个细节考虑完后，就基本没问题了。

**
总结：前段时间和女朋友出去玩了一圈，但是时间太短，实在没有能力与心情去享受旅途。
这一年，将会发生太多事，如果我们能走下来，我一定会去她家看望她的父母。
但是，要走下来，真的好难。
我们一定要，一起走过去！
**

Anyway, Good luck, Richardo!

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n <= 0)
            return head;
        if (head.next == null)
            return null;
        ListNode curr = head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        int counter = 1;
        while (counter < n) {
            counter++;
            curr = curr.next;
        }
        while (curr.next != null) {
            curr = curr.next;
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return dummy.next;
    }
}

采用了 dummy code后就一切变得方便了。
为什么需要dummy node？
因为有的时候head是可以被处理的，比如删除。他也需要有一个头，指着他。

Anyway, Good luck, Richardo!

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n < 0) {
            return null;
        }
        
        int total = 0;
        ListNode temp = head;
        while (temp != null) {
            total++;
            temp = temp.next;
        }
        
        n = total - n;
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode curr = dummy.next;
        ListNode pre = dummy;
        int counter = 0;
        while (curr != null) {
            if (counter == n) {
                pre.next = curr.next;
                break;
            }
            else {
                curr = curr.next;
                pre = pre.next;
                counter++;
            }
        }
        return dummy.next;
    }
}

two-pass

1. 遍历一遍获得链表结点总数
2. 删除

看了以前的解法才知道有更加简洁的做法。
重写一遍：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n < 0) {
            return null;
        }
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        int counter = 0;
        ListNode curr = dummy.next;
        ListNode pre = dummy;
        ListNode post = curr;
        
        while (post != null) {
            post = post.next;
            counter++;
            if (counter == n) {
                break;
            }
        }
        
        if (counter < n) {
            return dummy.next;
        }
        
        while (post != null) {
            pre = pre.next;
            curr = curr.next;
            post = post.next;
        }
        
        pre.next = curr.next;
        
        return dummy.next;
    }
}

差不多的做法。

Anyway, Good luck, Richardo! -- 08/15/2016