您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計疑難解答

C語言單鏈表全家桶：創建、遍歷、排序、反轉、查找中間節點完整實現

編輯：程式設計疑難解答

核心數據結構定義

typedef struct Node {
    int data;
    struct Node *next;
} Node;

五大核心操作實現

1. 尾插法創建（標準輸入讀取）

Node* CreateList() {
    Node *head = NULL, *tail = NULL, *p;
    int val;
    while (scanf("%d", &val) == 1) {
        p = (Node*)malloc(sizeof(Node));
        p->data = val;
        p->next = NULL;
        if (!head) head = p;
        else tail->next = p;
        tail = p;
    }
    return head;
}

2. 遍歷輸出

void PrintList(Node *head) {
    for (Node *p = head; p; p = p->next)
        printf("%d ", p->data);
    printf("\n");
}

3. 選擇排序（鏈表版）

Node* SortList(Node *head) {
    if (!head || !head->next) return head;
    Node *newHead = NULL, *newTail = NULL;
    while (head) {
        // 找最小節點及其前驅
        Node *min = head, *minPrev = NULL, *p = head, *prev = NULL;
        while (p->next) {
            if (p->next->data < min->data) {
                min = p->next;
                minPrev = p;
            }
            p = p->next;
        }
        // 從原鏈表摘除
        if (minPrev) minPrev->next = min->next;
        else head = head->next;
        // 接入新鏈表
        if (!newHead) newHead = newTail = min;
        else { newTail->next = min; newTail = min; }
    }
    if (newTail) newTail->next = NULL;
    return newHead;
}

4. 就地反轉（三指針法）

Node* ReverseList(Node *head) {
    Node *prev = NULL, *curr = head, *next;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev; // 新頭節點
}

5. 快慢指針找中間節點

Node* FindMiddle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow; // 偶數長度返回偏右中間
}

雙向鏈表擴展版

typedef struct DNode {
    int data;
    struct DNode *prev, *next;
} DNode;

DNode* CreateDList() {
    DNode *head = NULL, *tail = NULL, *p;
    int val;
    while (scanf("%d", &val) == 1) {
        p = (Node*)malloc(sizeof(DNode));
        p->data = val; p->prev = p->next = NULL;
        if (!head) head = p;
        else { tail->next = p; p->prev = tail; }
        tail = p;
    }
    return head;
}

void PrintDList(DNode *head) {
    DNode *p = head, *tail = NULL;
    while (p) { printf("%d ", p->data); tail = p; p = p->next; }
    printf("\n");
    while (tail) { printf("%d ", tail->data); tail = tail->prev; }
    printf("\n");
}