[数据结构与算法]单链表(快慢指针问题)

/*
 * 快慢指针:
 * 带有头结点的单链表L， 设计一个尽可能高效的算法求L中的中间结点
 */
#include "bits/stdc++.h"

using namespace std;

#define ERROR -1
#define OK 0

typedef struct LNode {
    int elem;//结点的数据域
    struct LNode *next;//结点的指针域
} LNode, *LinkList;

int TheTailInterpolation(LinkList &L, int n) {
    //尾插法创建单链表 单链表的顺序正好与输入的顺序相同
    //生成新的头结点 头结点的指针域设置为NULL
    LinkList s, r;
    L = new LNode;
    if (L == NULL) {
        cerr << "结点创建失败" << endl;
        return ERROR;
    }
    L->next = NULL;
    r = L;//尾指针指向头结点
    while (n--) {
        s = new LNode;//生成新的结点
        if (s == NULL) {
            cerr << "结点创建失败" << endl;
            return ERROR;
        }
        cout << "请输入您要插入的元素:" << endl;
        cin >> s->elem;//输入元素值赋给新结点的数据域
        s->next = NULL;
        r->next = s;
        r = s;
    }
    return OK;
}

LinkList FindMiddle(LinkList L) {
    LinkList p, q;
    p = L;//p为快指针 初始时指向L
    q = L;//q为慢指针 初始时指向L
    while ((p != NULL) && (p->next != NULL)) {
        p = p->next->next;//p为快指针一次走两步
        q = q->next;//q为慢指针一次走一步
    }
    return q;//返回中间结点指针
}

int ListPrint_L(LinkList L) {
    //单链表输出
    LinkList p;
    p = L->next;
    while (p != NULL) {
        cout << p->elem << "\t";
        p = p->next;
    }
    cout << endl;
}

int main() {
    LinkList L, mid;
    int i;
    cout << "创建单链表L:" << endl;
    cout << "请输入单链表的表长:" << endl;
    cin >> i;
    TheTailInterpolation(L, i);
    cout << "单链表的数据为:" << endl;
    ListPrint_L(L);
    mid = FindMiddle(L);
    cout << "单链表中间结点数据为:" << mid->elem << endl;
    return 0;
}

超强干货来袭

云风专访：近40年码龄，通宵达旦的技术人生