鏈表反轉完整實現：迭代法與記憶體管理

演算法核心思想

保留原鏈表頭節點，遍歷過程中用三個指標（head當前節點、mid新頭、last前一節點）逐一反轉next指標方向，最終mid指向新頭節點。

完整原始碼

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

struct llist {
    int num;
    struct llist *next;
};
typedef struct llist node;
typedef node *llink;

// 列印鏈表
void printllist(llink ptr) {
    while (ptr != NULL) {
        printf("[%d]", ptr->num);
        ptr = ptr->next;
    }
    printf("\n");
}

// 建立鏈表
llink createllist(int *array, int len) {
    llink head = (llink)malloc(sizeof(node));
    if (!head) return NULL;
    head->num = array[0];
    head->next = NULL;
    llink ptr = head;
    for (int i = 1; i < len; i++) {
        llink ptr1 = (llink)malloc(sizeof(node));
        if (!ptr1) return NULL;
        ptr1->num = array[i];
        ptr1->next = NULL;
        ptr->next = ptr1;
        ptr = ptr1;
    }
    return head;
}

// 核心：鏈表反轉
llink invertllist(llink head) {
    llink mid = NULL, last = NULL;
    while (head != NULL) {
        last = mid;
        mid = head;
        head = head->next;
        mid->next = last;
    }
    return mid;
}

// 釋放鏈表記憶體
void freellist(llink head) {
    llink ptr;
    while (head != NULL) {
        ptr = head;
        head = head->next;
        free(ptr);
    }
}

int main() {
    int data[6] = {1,2,3,4,5,6};
    llink head = createllist(data, 6);
    if (!head) exit(1);
    printllist(head);      // [1][2][3][4][5][6]
    head = invertllist(head);
    printllist(head);      // [6][5][4][3][2][1]
    freellist(head);
    return 0;
}

反轉過程圖解

初始:  head→1→2→3→4→5→6→NULL
       mid=NULL, last=NULL

第1輪: last=NULL, mid=1, head=2, 1→NULL
第2輪: last=1,   mid=2, head=3, 2→1
第3輪: last=2,   mid=3, head=4, 3→2
...
最終:  mid→6→5→4→3→2→1→NULL

關鍵點總結

• 三指標協作：head推進、mid建新鏈、last記錄前驅
• 原地反轉：空間複雜度O(1)，無需額外節點
• 記憶體安全：提供freellist避免洩漏
• 邊界處理：空鏈表、單節點均正確處理

複雜度分析