【数据结构】--单链表力扣面试题③找链表的中间节点

法一：遍历链表法

法二、快慢指针法

题述：给定一个头结点为head的非空单链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。

示例1：

输入：【1,2,3,4,5】

输出：此链表中的节点3（序列化形式【3,4,5】），返回的节点值为3.（测评系统对该节点序列化表述是【3,4,5】）。注意，我们返回了一个ListNode类型的对象ans，这样：ans.val = 3，ans.next.val = 4，ans.next.next.val = 5，以及ans.next.next.next.val = NULL。

题中已给链表的定义和链表头，让你完善middleNode函数

struct listnode
{
int val;
struct listnode* next;
};
struct listnode* middleNode(struct listnode* head)

法一：遍历链表法

遍历链表，算出链表长度n。再遍历到n/2。就能求出中间节点，这种方法的时间复杂度为n+n/2 = 3n/2 -> o(n),同样，这种方法对于是空链表的情况也适用，所以无需格外加判断。

#include<stdio.h>
#include<stdlib.h>struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{//法一、遍历链表法int len = 0;struct ListNode* cur = head;while (cur){len++;cur = cur->next;}cur = head;for (int i = 0; i < len / 2; i++){cur = cur->next;}return cur;//对于空链表也同样适用，直接返回NULL
}
int main()
{struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));n1->val = 1;n2->val = 2;n3->val = 3;n4->val = 4;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;struct ListNode* obj = middleNode(n1);if (obj)//一定要考虑链表为空的情况是不能打印的，会非法访问内存printf("%d\n", obj->val);elseprintf("链表为空，无法寻找！\n");return 0;
}

法二、快慢指针法

fast（快指针）slow（慢指针），使慢指针一次走一步，快指针一次走两步。那么针对有偶数个结点的链表，fast走到尾节点算终止条件。针对有奇数个结点的链表，fast走到NULL 算终止条件。无论偶数还是奇数个结点的链表，slow最后指向的节点就是中间节点。

注：快慢指针：本质上不说两个指针谁走的快，谁走的慢，而是指谁先走。先走多少步是可以自己设置的，本题就设置fast每次走2步，slow每次走1步。

法二是更优算法，可以实现只遍历链表一次

#include<stdio.h>
#include<stdlib.h>struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{//法二、快慢指针法struct ListNode* fast, * slow;fast = slow = head;//初始条件，快慢指针均为头指针while (fast && fast->next)//结束条件会因链表个数是奇偶个而判断条件不同{slow = slow->next;//慢指针每次走一步fast = fast->next->next;//快指针每次走两步}return slow;
}
int main()
{struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));n1->val = 1;n2->val = 2;n3->val = 3;n4->val = 4;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;struct ListNode* obj = middleNode(n1);if (obj)//一定要考虑链表为空的情况是不能打印的，会非法访问内存printf("%d\n", obj->val);elseprintf("链表为空，无法寻找！\n");return 0;
}