<算法>圖解逆序單向連結清單全過程

4個桶, 桶上都分别标着特定的标簽1, 2, 3, 4; 桶裡有對應的4個球,标着和桶一樣的編号;

問題來了, 讓所有桶和桶内球的編号之和都為5, 在交換的過程中,不能增加額外的桶, 且球不能着地,應該如何解決呢,最好的方式就是多找幾個人,手持球完成交換;

事實上, 在單向連結清單逆序的過程中: 我們也需要使用指針來代替人的作用

連結清單由多個結點組成, 每一個結點可被看做最小的機關.

要求在不開辟新記憶體空間的情況下,完成連結清單的逆序

1

2

3

4

5

6

7

8

# include <stdio.h>

// 定義連結清單結點
struct ListNode{
    // 定義結點的值
    int n_val;
    // 定義結點指向下一個結點的指針的值
    ListNode* p_next;
    // 結構體預設構造方法
    ListNode(int x): n_val(x), p_next(NULL) {};
};

// 定義逆序類
class Solution{
public:
    // 傳傳入連結表頭部結點的指針(直接用指針修改原數組 的排列情況)
    ListNode* reverseList(ListNode* head){
        // 建立一個新的ListNode類型的指針, 用于最後的傳回值(開辟第一個指針空間)
        ListNode *new_head = NULL;
        // 開始周遊整個連結清單, 重排為新的連結清單
        while(head){
            // 建立臨時結點, 存儲 目前head結點 的指向(開辟第二個指針空間)
            ListNode* tmp = head->p_next;
            // 将目前結點指向到 new_head
            head->p_next = new_head;
            // 将new_head指向head目前的結點
            new_head = head;
            // 将head結點後移一個機關;
            head = tmp;
        }
        return new_head;
    }
};

int main(){

    // 初始化值
    ListNode a(10);
    ListNode b(20);
    ListNode c(30);
    ListNode d(40);

    a.p_next = &b;
    b.p_next = &c;
    c.p_next = &d;
    d.p_next = NULL;

    // 執行個體化方法
    Solution solve;
    // 擷取連結清單頭指針
    ListNode *head = &a;

    printf("轉置之前的連結清單為:\n");
    while (head){
        // 列印目前指針所在結點的值
        printf("%d\n", head->n_val);
        // 指針後移
        head = head->p_next;
    }
    // 執行轉置
    head = solve.reverseList(&a);
    printf("轉置之後的連結清單為:\n");

    
    while (head) {
        printf("%d\n", head->n_val);
        head = head->p_next;
    }
    return 0;
}
           

逆序