力扣 876 链表中间结点

一开始延续回文链表向量数组的写法 只返回了结点值 且忘记向量可以为结点类型 导致出错

本题其实很简单 想的有点复杂了

1.向量数组

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> a= {head};
        while(a.back()->next)
            a.push_back(a.back()->next);
           return a[a.size()/2];//中间结点
     
    }
};
           

不用数组的求中点 两次遍历 系统会进行序列化

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
       ListNode*p=head;
       int n=0;
       while(p)
       {  
           ++n;
           p=p->next;
       }
       p=head;
       for(int i=0;i<n/2;++i)
       {
          p=p->next;
       }
       return p;//找到中点
      
     
    }
};
           

时间复杂度O(n)

空间复杂度O(n)

2.快慢指针 遍历一遍

慢指针走一步 快指针走两步 快指针遍历完 慢指针走到中点

注意 遍历结束 偶数 快指针不为空，取慢指针

奇数 快指针为空 取慢指针

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head==NULL) return head;
     ListNode *slow=head;//head第一个元素
     ListNode *fast=head;
     while(fast&&fast->next)
     {
         fast=fast->next->next;
         slow=slow->next;
     }
     return slow;
    }
};
           

时间复杂度O(n)

空间复杂度O(1)