【思考】从未知长度的单链表里，找到中间那个中间那个元素

常规想法

遍历一遍单链表，记录长度

再一次遍历，输出中间元素

这样的效率不是最优

另一种方式（来源于网络）

search 的速度是 mid 的两倍，search 走完恰好 mid 走一半

void printInt(intList *head){
    intList *mid,*search; // search 的速度是 mid 的两倍，search 走完恰好 mid 走一半

    mid = search = head;  // 保证 mid search 启点一样

    while (search->next != NULL){
        search = search->next;   // search 取下一个
        if (search->next != NULL){
            search = search->next;  // search 再去下一个
            mid = mid->next;     // mid 就取一次
        }else{
            mid = mid->next;     // search 取到头，mid 再往下取一位
        }
    }

    printf("\n %d ",mid->num);
}

完整代码

• 随机生成任意长度单链表
• 输出单链表值
• 输出位于中间的值
• 奇数个是最中间值，偶数个是中间两个的 前一个

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

typedef struct IntList{
    int num;
    struct intList *next;
} intList;

intList *applyList(); // 生成随机长度单链表
void printList(intList *head); // 查看单链表
void printInt(intList *head); // 输出单链表中间值

intList *applyList(){
    srand((unsigned)time(NULL));
    int len = rand() % 10 + 10; // 10 到 20的随机数

    intList *head = (intList *)malloc(sizeof(intList));
    if (head == NULL)exit(-1); // 链表头部申请失败
    head->next = NULL;

    while(len){
        intList *node = (intList *)malloc(sizeof(intList));
        node->num = rand() % 10 + 20;
        node->next = head->next;
        head->next = node;
        len--;
    }
    return head;
}

void printList(intList *head){
    intList *t = head->next;
    while(t){
        printf("%d ",t->num);
        t = t->next;
    }
};

void printInt(intList *head){
    intList *mid,*search; // search 的速度是 mid 的两倍，search 走完恰好 mid 走一半

    mid = search = head;  // 保证 mid search 启点一样

    while (search->next != NULL){
        search = search->next;   // search 取下一个
        if (search->next != NULL){
            search = search->next;  // search 再去下一个
            mid = mid->next;     // mid 就取一次
        }else{
            mid = mid->next;     // search 取到头，mid 再往下取一位
        }
    }

    printf("\n %d ",mid->num);
}

int main()
{
    intList *list = applyList(); // 随机生成单链表
    printList(list); // 查看链表的值
    printInt(list);  // 输出中间值
    return 0;
}