算法：如何返回链表的中间节点

有一个链表，这个链表如果是奇数个节点则返回链表的中间节点，如果是偶数个节点，则返回较后的节点部分

这里给出三种解法：

解法一：两次遍历
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int n = 0;
        ListNode* cur = head;
        while (cur) {  // 第一遍：数长度
            n++;
            cur = cur->next;
        }
        
        int mid = n / 2;
        cur = head;
        for (int i = 0; i < mid; i++) { // 第二遍：走到中间
            cur = cur->next;
        }
        return cur;
    }
};

时间：O(n)（实际上是 1.5n） | 空间：O(1)

解法二：快慢指针
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

时间：O(n) | 空间：O(1)（最优解）

解法三：数组存储法（空间换时间）
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> v;
        while (head) {
            v.push_back(head);
            head = head->next;
        }
        return v[v.size() / 2];
    }
};

O(n) | 空间：O(n)（不推荐大数据量，但写起来最快）

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2302_80141451/article/details/162737004