面试金典题2.3

若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。

假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。

例如，传入节点 c（位于单向链表 a->b->c->d->e->f 中），将其删除后，剩余链表为 a->b->d->e->f

示例：

输入：节点 5 （位于单向链表 4->5->1->9 中）
输出：不返回任何数据，从链表中删除传入的节点 5，使链表变为 4->1->9

这道题的方法很简单，只要清楚链表的储存方式就可以。已知给出的中间节点为node，那么我们想要删除这个节点，只需要将这个节点的值变为下一个节点的值，我们就得到了两个值相同的节点，然后我们将下下个节点指向需要删除节点的下一个节点，就完成删除了。实际上是删除了中间节点的下一个节点，但是因为我们因为将下一个节点的值赋给中间节点，因此，我们可以直接删除中间节点的下一个节点。这样说可能不太清楚，其实我们把我们要删除的节点定义为当前节点，那么我们就可以直接让当前节点的前驱节点指向后继节点就实现了删除。类比到这个题里，当前节点并不是题目中给出的中间节点，而是它的下一个节点，因此我们先将中间节点的值变为下一个节点的值，再删除下一个节点，那么实际看到的结果就是删除了中间节点。

leetcode代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val=node->next->val;
        node->next=node->next->next;
    }
};

其实我一开始没有注意到这个题是直接给出要删除的节点，我以为的中间节点是要自己找的。理解错题意了。那么如果要找真正意义上的中间节点该怎么做呢？请往下看

其实找中间节点，主要是看数的总数为偶数的情况，到底是选择靠前的那个节点还是靠后的节点，而思路和上一个找倒数第k个节点的题类似，都是使用双指针去找，同样将两个指针先指向头节点，而中间节点就是在1/2的位置，那么我们只要让两个指针的移动速度为两倍差，但是如果数的个数为偶数的话，那么找到的节点就是靠后的那个节点。

leetcode代码

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head==nullptr&&head->next==nullptr){
            return head;
        }
        ListNode *p = head;
        ListNode *q = head;
        while(p != nullptr && q->next != nullptr) {
            q = q->next;
            p = p->next->next;
        }
        return q;
    } 
};

那么如果我们要找到的是靠前的那个节点呢？

class Solution {  
public:  
    ListNode* middleNode(ListNode* head) {  
        if (head == nullptr || head->next == nullptr) {  
            // 如果链表为空或只有一个节点，则直接返回头节点  
            return head;  
        }  
  
        ListNode *p = head;  
        ListNode *q = head;  
        while (p->next != nullptr && p->next->next != nullptr) {  
            // p 每次移动两步，直到 p->next 或 p->next->next 为空  
            p = p->next->next;  
            // q 每次移动一步  
            q = q->next;  
        }  
        // 当 p 无法再安全地前进两步时（即 p->next 或 p->next->next 为空），q 指向“靠前的”中间节点  
        return q;  
    }  
};