P52 移除单链表倒数第 n 个节点

描述#

这个题目说的是，给你一个单链表和数字 n，你要移除单链表倒数第 n 个节点，然后返回单链表。

比如说，给你的单链表是：
1 -> 2 -> 4 -> 8
给你的数字 n 是 3，单链表中倒数第 3 个节点是 2，移除 2 以后的单链表是：
1 -> 4 -> 8

代码#

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(k), Space: O(1)
  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode p = dummy, q = dummy;

    for (; n > 0 && q.next != null; --n) q = q.next;
    if (n != 0) return dummy.next;

    while (q.next != null) {
      p = p.next;
      q = q.next;
    }
    p.next = p.next.next;
    return dummy.next;
  }

}