LeetCodeDay11

237. 删除链表中的节点

描述

• 请编写一个函数，使其可以删除某个链表中给定的（非末尾的）节点，您将只被给予要求被删除的节点。

示例

• 假设该链表为 1 -> 2 -> 3 -> 4，给定您的为该链表中值为3的第三个节点，那么在调用了您的函数之后，该链表则应变成 1 -> 2 -> 4 。

思路

1. 只给出了待删除的节点，没有给头节点，因此只能拿到删除节点的后续节点。
2. 将后续节点复制到当前节点，然后删除后续节点

struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(NULL) {}
};
class Solution_237 {
 public:
  void deleteNode(ListNode* node) {
    if (node == NULL) return;
    ListNode* nextNode = node->next;
    if (nextNode) {
      node->val = nextNode->val;
      node->next = nextNode->next;
      free(nextNode);
    }
  }
};

19. 删除链表的倒数第N个节点

描述

• 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例

• 给定一个链表: 1->2->3->4->5, 和 n = 2.
• 当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明

给定的 n 保证是有效的。

进阶

你能尝试使用一趟扫描实现吗？

思路

1. 直观解法，倒数第n个即是正数第Size-n+1个。先遍历出长度，在遍历找到要删除的节点，总共需遍历两次。
2. 遍历优化二，空间换时间。维系一个Vector保存遍历过的每个节点。这样遍历过一次后就能直接找出倒数第n个进行移除。
3. 最优解，利用两个相隔n的指针。第一个指针向后先走n步，然后两个指针一起走，最后当前序指针走到末端后，后续指针即为所求。

Tips

1. 利用一个指向头结点的节点来保证每个节点都有前向节点。一方面可以避免处理删除头结点的问题，另一方面可以从指向头结点的节点开始遍历，避免找到删除节点后，找不到对应的前序节点进行删除操作。（注意此时后续指针的下一个节点才为所求）
2. 单向链表中删除一个节点，其实就是要找到它的前序节点，即node->next为所求。这样便于删除操作。

class Solution_19_01 {
 public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (head == NULL) return NULL;
    int size = 0;
    ListNode* tmp = head;
    while (tmp) {
      ++size;
      tmp = tmp->next;
    }
    if (n > size) return NULL;
    ListNode* pre = NULL;
    ListNode* node = head;
    ListNode* next = head->next;
    for (int i = 1; i < size - n + 1; ++i) {
      pre = node;
      node = next;
      next = next->next;
    }
    ListNode* newHead = (node == head ? head->next : head);
    if (pre) {
      pre->next = next;
      free(node);
    }
    return newHead;
  }
};

class Solution_19_02 {
 public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (head == NULL) return NULL;
    vector<ListNode*> lists;
    ListNode* tmp = head;
    while (tmp) {
      lists.push_back(tmp);
      tmp = tmp->next;
    }
    ListNode* pre = lists.size() == n ? NULL : lists[lists.size() - n - 1];
    ListNode* node = lists[lists.size() - n];
    ListNode* newHead = (node == head ? head->next : head);
    if (pre) {
      pre->next = node->next;
      free(node);
    }
    return newHead;
  }
};

// 利用一个指向头结点的节点来保证每个节点都有前向节点，避免处理删除头结点的问题
class Solution_19_03 {
 public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* tag = new ListNode(0);
    tag->next = head; // 构建一个指向头结点的节点
    ListNode* tmp = tag;
    for (int i = 0; i < n; ++i) {
      head = head->next;
    }
    while (head != NULL) {
      head = head->next;
      tmp = tmp->next;
    }
    // tmp节点的下一个为要删除的节点
    tmp->next = tmp->next->next;
    return tag->next;
  }
};