给定 N 给出一个单链表，不知道节点N的值，怎样只遍历一次就可以求出中间结点。输入样例:3 -> 4 -> 7 -> 9 ->12 ->5 ->8

解题思路：

快慢指针法，即使用两个指针，一个指针每次走两步，一个指针每次走一步，当快指针走到链表末尾时，慢指针就到了链表的中间。

算法步骤：

1.定义快慢指针，初始化为head节点。

2.循环遍历链表，快指针每次走两步，慢指针每次走一步。

3.当快指针走到链表末尾时，慢指针就到了链表的中间。

4.返回慢指针指向的节点即可。

Python代码实现：

相关问题

用c语言编写程序 找出两个链表的公共结点 【问题描述】给定两个单链表，编写算法找出两个链表的公共结点。 【输入形式】 四行： 第一行：一个数字（第一个单链表中的元素个数） 第二行：第一个单链表中各个结点的值 第三行：一个数字（第二个单链表中的元素个数） 第四行：第二个单链表中各个结点的值 【输出形式】 两行： 第一行：两个单链表的公共元素个数 第二行：依次打印输出各个公共元素 【样例输入】 6 12 5 8 9 -23 16 4 16 21 9 3 【样例输出】 2 9 16 注：若两个链表无公共元素，则输出： 0 没有公共元素

#include <stdio.h>
#include <stdlib.h>

// 定义链表结构体
typedef struct Node {
int data;
struct Node *next;
} Node;

// 创建链表
Node* createList(int n) {
Node *head = NULL, *tail = NULL;
for (int i = 0; i < n; i++) {
Node *node = (Node*)malloc(sizeof(Node));
scanf("%d", &node->data);
node->next = NULL;
if (tail == NULL) {
head = tail = node;
} else {
tail->next = node;
tail = node;
}
}
return head;
}

// 遍历链表
void traverseList(Node *head) {
Node *p = head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}

// 获取链表长度
int getListLength(Node *head) {
int len = 0;
Node *p = head;
while (p != NULL) {
len++;
p = p->next;
}
return len;
}

// 找到两个链表的公共节点
Node* findCommonNode(Node *head1, Node *head2, int *count) {
int len1 = getListLength(head1);
int len2 = getListLength(head2);
Node *p1 = head1;
Node *p2 = head2;
// 将两个链表的长度调整为相等
if (len1 > len2) {
for (int i = 0; i < len1 - len2; i++) {
p1 = p1->next;
}
} else {
for (int i = 0; i < len2 - len1; i++) {
p2 = p2->next;
}
}
// 查找公共节点
Node *common = NULL;
while (p1 != NULL && p2 != NULL) {
if (p1->data == p2->data) {
if (common == NULL) {
common = p1;
}
(*count)++;
} else {
common = NULL;
*count = 0;
}
p1 = p1->next;
p2 = p2->next;
}
return common;
}

int main() {
int n1, n2;
scanf("%d", &n1);
Node *head1 = createList(n1);
scanf("%d", &n2);
Node *head2 = createList(n2);
int count = 0;
Node *common = findCommonNode(head1, head2, &count);
if (common == NULL) {
printf("0 没有公共元素\n");
} else {
printf("%d ", count);
while (common != NULL) {
printf("%d ", common->data);
common = common->next;
}
}
return 0;
}

题目描述： 给定一棵完全二叉树，要求对其进行层序遍历。 输入格式： 第一行给出一个正整数 N (≤1000)，是该树的结点数。下一行给出 N 个正整数，即该树的各个结点的编号（从 0 开始编号），顺序为按层序遍历的顺序给出，即对于编号为 i 的结点，其左右儿子分别为 2i+1 和 2i+2（若某个儿子不存在，则结点为空）。 输出格式： 对该树进行层序遍历，输出每个结点的编号。 输入样例： 9 0 1 2 3 4 5 6 -1 -1 输出样例： 0 1 2 3 4 5 6

以下是ChitGPT的回答：

树的层序遍历可以使用队列来实现。从根节点开始，将其入队，然后依次将队首结点出队并访问，若其有左儿子，则将左儿子入队，若有右儿子，则将右儿子入队。直到队列为空，遍历结束。

下面是实现该算法的代码：

#include <iostream>
#include <queue>
using namespace std;

const int N = 1010;

int n;
int a[N]; // 存储每个结点的编号
queue<int> q;

int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];

q.push(a[0]);
while (!q.empty())
{
int t = q.front(); q.pop();
if (t == -1) continue;
cout << t << ' ';
q.push(a[t * 2 + 1]);
q.push(a[t * 2 + 2]);
}

return 0;
}