给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
# 链表的结点数范围是 [1, 100]
核心思想是使用快慢指针法，快指针一次走两步，慢指针一次走一步，这样快指针永远都是慢指针的两倍，当快指针走完的时候，慢指针正好在快指针的中间位置。
Python写法
# 定义单链表
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 尾插法定义链表
def creat_linklidt_tail(li):
head = ListNode(None)
tail = head
for element in li:
node = ListNode(element)
tail.next = node
tail = node
return head.next
# shift+tab整体取消缩进
# 快慢指针，快指针行进永远是慢指针的两倍，快指针走完慢指针走一半
def middleNode(head: ListNode):
fast, slow = head, head
# 快指针和快指针的下一个节点都不为零，考虑到两个中间值的问题
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 链表转为列表
def tolist(head: ListNode):
res = []
while head:
res.append(head.val)
head = head.next
return res
a = creat_linklidt_tail([1, 2, 3, 4, 5]) # a即是链表的头部
b = tolist(a)
# 打印列表
for i in range(len(b)):
print(b[i])
print("链表的中间值为", middleNode(a).val)
print("链表的头部为", a.val)
C语言写法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义单链表
struct ListNode {
int val;
struct ListNode *next;
};
// 创建单链表
struct ListNode *creList(int *a, int size) {
struct ListNode *head, *p, *s;
int i = 0;
printf("链表的长度为：%d\n", size);
head = (struct ListNode *)malloc(sizeof(struct ListNode));
head->next = NULL;
p = head;
for (i = 0; i < size; i++) {
s = (struct ListNode *)malloc(sizeof(struct ListNode));
s->val = a[i];
p->next = s;
s->next = NULL;
p = s;
}
return head->next;
}
// 返回链表中间值
struct ListNode *middleNode(struct ListNode *head) {
struct ListNode *fast = head, *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
int main() {
int a[] = {0, 1, 2, 3};
int n = sizeof(a) / sizeof(int);
printf("a的长度为：%d\n", n);
struct ListNode *head, *temp;
head = creList(a, n);
printf("链表第一个元素：%d\n", head->val);
temp = head;
while (temp) {
printf("%d\n", temp->val);
temp = temp->next;
}
// 打印链表中间值
printf("链表的中间值为：%d\n", middleNode(head)->val);
free(head);
}
