19. [M] Remove Nth Node From End of List

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/submissions/

难点还是在于细节和边界处理上。

基本思路是,用前后两个指针,拉开 n 个节点的距离。然后同步移动直到前面的节点到链表尾部,那么后面那个指针指向的就是要删掉的节点。难点在于如何处理要删除的节点是头节点。为了简化逻辑,还是创建一个伪头节点,这样处理删除头节点的情况就比较统一了。

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode p = dummy, c = dummy;
// input: [1,2] n = 2
// (dummy/p/c) -> (1) -> (2) -> (null)
for (int i = 0; i < n; i++) {
c = c.next;
}
// (dummy/p) -> (1) -> (2/c) -> (null)
while (c.next != null) {
c = c.next;
p = p.next;
}
// (dummy/p) -> (2/c) -> (null)
p.next = p.next.next;
return dummy.next;
}
}