19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Solution1:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

// two-pass, 扫描两遍, 保存前一个结点的方法
class Solution {
 public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (head == nullptr) return head;
    ListNode* prev = head, *p = prev->next;
    int size = 1;
    while (p) {
      prev = prev->next;
      p = prev->next;
      size++;
    }

    prev = head; p = prev->next;
    for (int i = 0; i < size-n-1; i++) {
      prev = prev->next;
      p = prev->next;
    }

    if (prev && !p) {
      prev = nullptr;
      delete(prev); delete(p);
      head = nullptr;
    } else {
      if (prev == head && size-n == 0) {
        delete(prev);
        head = p;
      } else {
        prev->next = p->next;
        delete(p);
      }
    }
    return head;
  }
};

Solution2:

一个node先在原地等待, 当p到达n=1的位置时候, cur和p一起移动, 当p移动到最后一个结点时， cur就是要删除的结点。

// one-pass, 更新删除结点的操作
class Solution {
 public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (head == nullptr || n == 0) return head;

    ListNode *cur = head, *p = head;
    for (int i = 0; p->next; i++) {
      if (i >= n-1) cur = cur->next;
      p = p->next;
    }
    
    
    // 删除cur结点的操作
    if (cur->next != nullptr) {   // cur不是尾结点
      ListNode *delNode = cur->next;
      cur->val = delNode->val;
      cur->next = delNode->next;
      delete(delNode);
      delNode = nullptr;
    } else if (cur == head) {     // cur既是头结点也是尾结点
      delete(cur);
      cur = nullptr;
      head = nullptr;
    } else {                      // cur是尾结点
      p = head;
      while (p->next != cur) {
        p = p->next;
      }
      p->next = nullptr;
      delete(cur);
      cur = nullptr;
    }
    return head;
  }
};

删除链表结点的操作要记得熟练.
先讨论不是尾结点, 再讨论既是尾结点也是头结点, 最后讨论尾结点.