面试题：C语言指针算术运算在复杂数据结构中的应用

Question

假设有一个自定义的结构体链表，结构体定义如下：struct Node { int data; struct Node *next; }; 编写一个函数，该函数接收链表头指针，通过指针算术运算找到链表中间节点（如果链表长度为偶数，返回中间两个节点中的任意一个），并返回该节点的指针。请详细阐述你的算法思路以及指针算术运算在其中是如何实现的，同时分析该方法在不同链表长度情况下的时间复杂度。

Answer 1

1. 算法思路：
   • 使用快慢指针法。定义两个指针，一个快指针fast，一个慢指针slow，都从链表头开始。
   • 快指针每次移动两步，慢指针每次移动一步。
   • 当快指针到达链表末尾（fast == NULL或者fast->next == NULL）时，慢指针就指向了链表的中间节点。
2. 指针算术运算实现：
   • 在代码中，fast = fast->next->next;实现了快指针每次移动两步，这就是指针算术运算的体现，通过->操作符访问下一个节点的下一个节点。slow = slow->next;实现了慢指针每次移动一步。
3. 代码实现：

struct Node {
    int data;
    struct Node *next;
};

struct Node* findMiddle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;
    while (fast!= NULL && fast->next!= NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

4. 时间复杂度分析：
   • 链表长度为奇数：假设链表长度为n，快指针移动到链表末尾时，移动的次数为n/2（向下取整）。慢指针移动到中间节点，移动次数也为n/2（向下取整）。因为每次移动操作时间复杂度为O(1)，所以总的时间复杂度为O(n/2)，也就是O(n)。
   • 链表长度为偶数：同样，快指针移动到链表末尾时，移动的次数为n/2。慢指针移动到中间两个节点中的一个，移动次数也为n/2。每次移动操作时间复杂度为O(1)，所以总的时间复杂度为O(n/2)，也就是O(n)。

综上所述，该方法在不同链表长度情况下的时间复杂度均为O(n)。