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

struct ListNode {
int val;
struct ListNode *next;
};

struct ListNode* middleNode(struct ListNode* head) {
struct ListNode *slow = head, *fast = head;
while (fast && fast->next) { // 快指针每次走两步，慢指针每次走一步
slow = slow->next;
fast = fast->next->next;
}
return slow;
}

相关问题

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

解题思路：

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

算法步骤：

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

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

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

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

Python代码实现：

编写程序，建立2个带头结点单链表，输入若干整数将正整数插入第1个单链表，将负整数插入第2个单链表，插入前和插入后单链表保持递增或相等次序，显示2个单链表，最后销毁。程序不可存在内存泄漏。基础上合并2个单链表，合并前后单链表保持递增或相等次序，显示合并前后单链表。注意不可存在内存泄漏。 输入格式: 若干整数。 输出格式: 每个单链表输出占一行，元素间用分隔符分隔；共3行 输入样例: 100 2 3 -2 -8 -6 -9 -10 50 2 -1 输出样例: 2->2->3->50->100 -10->-9->-8->-6->-2->-1 -10->-9->-8->-6->-2->-1->2->2->3->50->100

以下是实现该功能的 C++ 代码：

#include <iostream>
using namespace std;

// 定义链表结点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(NULL) {}
};

// 在带头结点的单链表中插入一个结点
void insert(ListNode* head, int x) {
    ListNode* p = head;
    while (p->next != NULL && p->next->val < x) {
        p = p->next;
    }
    ListNode* new_node = new ListNode(x);
    new_node->next = p->next;
    p->next = new_node;
}

// 销毁带头结点的单链表
void destroy(ListNode* head) {
    while (head != NULL) {
        ListNode* p = head;
        head = head->next;
        delete p;
    }
}

// 合并两个带头结点的单链表
ListNode* merge(ListNode* head1, ListNode* head2) {
    ListNode* p1 = head1->next;
    ListNode* p2 = head2->next;
    ListNode* new_head = new ListNode(0);
    ListNode* p = new_head;
    while (p1 != NULL && p2 != NULL) {
        if (p1->val <= p2->val) {
            p->next = p1;
            p1 = p1->next;
        } else {
            p->next = p2;
            p2 = p2->next;
        }
        p = p->next;
    }
    if (p1 != NULL) {
        p->next = p1;
    }
    if (p2 != NULL) {
        p->next = p2;
    }
    ListNode* result = new_head->next;
    delete new_head;
    return result;
}

int main() {
    // 建立两个带头结点的单链表
    ListNode* head1 = new ListNode(0);
    ListNode* head2 = new ListNode(0);
    int x;
    while (cin >> x) {
        if (x > 0) {
            insert(head1, x);
        } else {
            insert(head2, x);
        }
    }
    // 输出第一个单链表
    ListNode* p = head1->next;
    while (p != NULL) {
        cout << p->val << "->";
        p = p->next;
    }
    cout << "NULL" << endl;
    // 输出第二个单链表
    p = head2->next;
    while (p != NULL) {
        cout << p->val << "->";
        p = p->next;
    }
    cout << "NULL" << endl;
    // 合并两个单链表
    ListNode* merged_head = merge(head1, head2);
    // 输出合并后的单链表
    p = merged_head;
    while (p != NULL) {
        cout << p->val << "->";
        p = p->next;
    }
    cout << "NULL" << endl;
    // 销毁所有单链表
    destroy(head1);
    destroy(head2);
    destroy(merged_head);
    return 0;
}

时间复杂度是 $O(n)$，其中 $n$ 是输入的整数的个数。