单链表综合练习：删除指定值节点、反转链表及查找中间节点

2.2 算法原理

注 1：n3 会最先指向 NULL 所以要特判； 注 2：链表可能为空，为空直接返回。

2.3 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;

struct ListNode* reverseList(struct ListNode* head) {
    // 链表为空
    if (head == NULL) return head;
    
    ListNode* n1 = NULL;
    ListNode* n2 = head;
    ListNode* n3 = head->next;
    
    while (n2) {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3) n3 = n3->next;
    }
    return n1;
}

三、链表中间节点

3.1 题目

链接：链表中间节点

3.2 算法原理

核心思想：快慢指针（2*slow == fast）

注意：不能 fast->next && fast，当遇到偶数链表会造成对空指针解引用。

3.3 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;

struct ListNode* middleNode(struct ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}