c語(yǔ)言單鏈表反轉(zhuǎn)的方法是什么

小億
92
2023-12-01 22:39:14

C語(yǔ)言中單鏈表的反轉(zhuǎn)可以通過(guò)修改指針的指向來(lái)實(shí)現(xiàn)。具體的方法如下：

  1. 定義三個(gè)指針：prev、curr和next。初始時(shí)，prev指向NULL，curr指向鏈表的頭節(jié)點(diǎn)，next指向curr的下一個(gè)節(jié)點(diǎn)。

  2. 遍歷鏈表，直到curr指向NULL為止，循環(huán)執(zhí)行以下操作： a. 將next指向curr的下一個(gè)節(jié)點(diǎn)，以便保留鏈表的連接關(guān)系。 b. 將curr的next指針指向prev，即將curr的指針?lè)较蚍崔D(zhuǎn)。 c. 將prev指向curr，以便保留反轉(zhuǎn)后的鏈表的頭節(jié)點(diǎn)。 d. 將curr指向next，以便繼續(xù)遍歷鏈表。

  3. 遍歷結(jié)束后，prev指向反轉(zhuǎn)后的鏈表的頭節(jié)點(diǎn)，即完成了鏈表的反轉(zhuǎn)。

以下是一個(gè)示例代碼：

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

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

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL;
    struct ListNode *curr = head;
    
    while (curr != NULL) {
        struct ListNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

int main() {
    // 創(chuàng)建鏈表 1->2->3->4->5
    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *node2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *node3 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *node4 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *node5 = (struct ListNode *)malloc(sizeof(struct ListNode));
    
    head->val = 1;
    head->next = node2;
    
    node2->val = 2;
    node2->next = node3;
    
    node3->val = 3;
    node3->next = node4;
    
    node4->val = 4;
    node4->next = node5;
    
    node5->val = 5;
    node5->next = NULL;
    
    // 反轉(zhuǎn)鏈表
    struct ListNode *newHead = reverseList(head);
    
    // 遍歷打印反轉(zhuǎn)后的鏈表
    struct ListNode *current = newHead;
    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }
    
    return 0;
}

運(yùn)行以上代碼，輸出結(jié)果為：5 4 3 2 1，即鏈表反轉(zhuǎn)成功。

0 踩