数据结构 ——— 单链表oj题：返回链表的中间节点

目录

题目要求

手搓简易单链表

代码实现

---

题目要求

给你单链表的头节点 head ，请你找出并返回链表的中间节点

如果有两个中间节点，则返回第二个中间节点

要求算法的时间复杂度为：O(N)

---

手搓简易单链表

代码演示：

// 单链表中数据的类型
typedef int SLTDataType;struct ListNode
{SLTDataType val; //单链表的数据struct ListNode* next; //指向下一个节点的指针
};// 手搓单链表
int main()
{struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));assert(n1);struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));assert(n2);struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));assert(n3);struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));assert(n4);struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));assert(n5);n1->val = 1;n2->val = 2;n3->val = 3;n4->val = 4;n5->val = 5;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = NULL;return 0;
}

---

代码实现

代码演示（快慢指针）：

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

代码解析：

slow 指针一次走一步，fast 指针一次走两步，那么 fast 指针就是 slow 指针的二倍
当链表节点为奇数个时：fast 指针走到尾节点，slow节点就是中间节点
当链表节点为偶数个时：fast 指针走到空，slow节点就是中间节点

代码验证：

单链表节点为奇数个时：

单链表节点为偶数个时：

算法的时间复杂度和空间复杂度：

while 循环执行了 N 次，且每次内部循环是常数次，且没有开辟额外的空间

算法的时间复杂度（大O渐进表示法）：O(N)

算法的空间复杂度（大O渐进表示法）：O(1)