題目

給你單鏈表的頭節點 head ，請你反轉鏈表，并回傳反轉后的鏈表，

鏈接：https://leetcode-cn.com/problems/reverse-linked-list/submissions/

分析

這里我們用兩種方法實作：

①調整鏈表方向

在這里插入圖片描述

按照上述分析，我們可以得出代碼：

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;

    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
        	n3 = n3->next;
    }
    return n1;
}

可當我們運行時，我們得出的結果為：

在這里插入圖片描述
這里說我們存在空指標的問題，我們再一次畫圖分析

在這里插入圖片描述
此時我們的n3指標指向空，我們在這一趟進行調整元素間的箭頭時，調整失敗，所以我們增加對n3
指標的判斷

    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
        	n3 = n3->next;
    }

這個時候我們在運行代碼，我們得出的結果為
在這里插入圖片描述
這個時候我們得出我們為考慮如果我們要反轉的鏈表為NULL的情況，所以我們增加對鏈表的判斷

if(head == NULL)
        return head;

此時，我們再一次運行代碼得出
在這里插入圖片描述

②頭插法

這里我們對題目中給出的例子再進行分析
在這里插入圖片描述
如果有不熟悉鏈表中頭插介面的實作，可以瀏覽/復習
https://blog.csdn.net/weixin_52664715/article/details/120336834?spm=1001.2014.3001.5501

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;//我們先保存cur的下一個節點的地址
        cur->next = newhead;//讓cur指向newhead
        newhead = cur;//讓newhead移動，為了讓下一個元素指向頭結點
        cur = next;
    }
    return newhead;
}

此時，我們運行代碼得出
在這里插入圖片描述

代碼

①

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL)
        return head;

    struct ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;

    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
            n3 = n3->next;
    }

    return n1;
    
}

②

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

總結

我們在解決題目時，經常會使用我們在學習時學習的介面內容，所以我們對常見的介面進行復習和擴展，因為我們上述題目在使用頭插法時與我們學習時的介面內容并不相同，但兩者的思路相同

以上就是我對這種方法的個人理解

上述內容如果有錯誤的地方，還麻煩各位大佬指教【膜拜各位了】【膜拜各位了】
在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/312125.html

標籤：其他

上一篇：資料結構單鏈表SingleLinkedList，Java實作單鏈表增刪改查

下一篇：虛擬機與Linu系統安裝與配置詳細教程