LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.


Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham
class Solution {
 public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* p = dummy;
    ListNode* q = dummy;
    for (int i = 0; i < n + 1; ++i) {
      p = p->next;
    }  // p 移动 n + 1 次指向第 n + 1 个节点
    // 此时 p 与 q 距离为 n + 1
    while (p) {
      p = p->next;  // p 到达最后的空节点时
      q = q->next;  // q 到达倒数第 n + 1 个节点
    }
    // 要删除倒数第 n 个节点
    // 让倒数第 n + 1 个节点的下一节点指向倒数第 n - 1 个节点即可
    q->next = q->next->next;
    return dummy->next;
  }
};