做了这么多linked list的题，其实可以看出:

  1. 一般都要遍历，分为one-pass, two-pass
  2. one-pass用一个额外的node就行了，two-pass需要双指针;
  3. Nth node, Kth node这种要找到特定的位置的节点, 就是上面这种情况;
  4. 一般都要创建一个node进行操作, 双指针的时候一般创建两个
  5. return head有时候要注意，因为head可能没有了(只有一个节点，这个节点被删掉了)

如果会有一个节点的误差，容易弄错，应该画个图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        ListNode slow = start, fast = start;
        fast.next = head;
        
        // gap n nodes
        // 1,2,3,4,5; slow:1, fast:3
        for (int i = 1; i < n+1; ++i) {
            fast = fast.next;
        }
        
        // exit: fast at last node, slow right before Nth node
        // fast:5, slow:3
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // skip Nth node from last
        slow.next = slow.next.next;
        return start.next;
    }

或者:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        ListNode slow = start, fast = start;
        fast.next = head;
        
        // gap n nodes
        // 1,2,3,4,5; slow:1, fast:4
        for (int i = 1; i <= n+1; ++i) {
            fast = fast.next;
        }
        
        // exit: fast at last node, slow right before Nth node
        // fast:null; slow: 3
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // skip Nth node from last
        slow.next = slow.next.next;
        return start.next;
    }