19. Remove Nth Node From End of List

T: O(n)

S: O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode delete = findNthFromEnd(dummy, n + 1); // should use dummy node, or in [1] n =1 case, p1.next will be null, or change findNthFromEnd's implementation
        // and notice, to delete n from end, we should find n+1 from end
        delete.next = delete.next.next;
        return dummy.next;
    }
    private ListNode findNthFromEnd(ListNode head, int k) {
        ListNode p1 = head;
        // p1 go k step   
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }
        ListNode p2 = head;
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}

/*
           n-k
            | 
--------------------
      k    n-k
      
      so we want go n -k steps, so move p1 to k, then p2 in head , with p1 go together, when p1 go to the end
      p2 has gone n-k steps, that ans
      
      
      
      in order to delete n from end
      find n+1 from end to delete 
      
      ------n+1---n------
      
*/