反轉單鏈表

題目
思路一：
- ??反轉？
- ?? 迭代向后挪動？
- ?? 終止條件？
思路二：
- ??頭插
- ?? 迭代挪動
- ??終止條件

題目

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

//Definition for singly-linked list：
struct ListNode {
    int val;
    struct ListNode *next;
 };

函式介面：

struct ListNode* reverseList(struct ListNode* head){

}

在這里插入圖片描述
反轉一個單鏈表: OJ鏈接

思路一：

改變“箭頭”指向
在這里插入圖片描述

??反轉？

在這里插入圖片描述
顯然我們需要兩個指標來負責反轉(n1,n2)，然而在反轉的同時(n2->next = n1;),原本①和②之間的鏈接也斷開了，這我們就需要第三個指標來記錄下一個節點的位置(n3)

因此，我們定義了如下三個指標并初始化

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

其中，n1,n2負責反轉，n3負責記錄，

n2->next = n1;//反轉

?? 迭代向后挪動？

挪動程序：
在這里插入圖片描述
可以很輕易的寫出代碼：

n1 = n2;
n2 = n3;
n3 = n3->next;

?? 終止條件？

快進~
在這里插入圖片描述
因此在n2->next==NULL時，回圈結束（注意，回圈括號內，想的是終止條件，寫的是進行條件），

while (n2 != NULL)
{
	//翻轉
	n2->next = n1;
	//迭代向后挪
	n1 = n2;
	n2 = n3;
	n3 = n3->next;
}

細心的小伙伴可能已經發現了，在這一次反轉之后的迭代挪動中，n3 = n3->next;是對空指標的解參考😱,會崩掉，不過沒關系啦，做一下處理就好了！

if(n3 != NULL)
	 n3 = n3->next;

在這里插入圖片描述
看圖！此時，我們要回傳鏈表的頭結點為n1

這里給出完整代碼：

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)
    {
        return NULL;//處理空鏈表
    }
    //初始條件
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;//n1,n2用來交換
    struct ListNode* n3 = head->next;//n3用來記錄下一個
    while(n2!=NULL)
    {
        //翻轉
        n2->next = n1;
        //迭代向后挪
        n1 = n2;
        n2 = n3;
        if(n3)
            n3 = n3->next;
    }
    return n1;
}

思路二：

🔑 取原鏈表節點，頭插到newhead新鏈表中去

有過思路一的詳細鋪墊，思路二分析起來就很簡單咯！
在這里插入圖片描述
定義指標并初始化：

struct ListNode* cur = head;
struct ListNode* next = head->next;
struct ListNode* newhead = NULL;//新鏈表的頭

??頭插

在這里插入圖片描述

//頭插
cur->next = newhead;
newhead = cur;

?? 迭代挪動

在這里插入圖片描述

??終止條件

快進~
在這里插入圖片描述

while (cur != NULL)
{
	//頭插
	cur->next = newhead;
	newhead = cur;
	//迭代往后挪
	cur = next;
	if (next)
		next = next->next;
}

給出完整代碼:

struct ListNode* reverseList(struct ListNode* head){
     if(head == NULL)
     {
         return head;//處理空鏈表
     }
     //初始化
     struct ListNode* cur = head;
     struct ListNode* next = head->next;
     struct ListNode* newhead = NULL;//新鏈表的頭
     while(cur!=NULL)
     {
        //頭插
        cur->next = newhead;
        newhead = cur;
        //迭代往后挪
        cur = next;
        if(next)
            next = next->next;
     }
     return newhead;
}

那么下面這樣寫也是可的，而且這里不需要再處理空鏈表，也無需處理next = next->next;在末尾會發生空指標的解參考問題，

這是由于迭代寫法上有一點點的小改變(struct ListNode* next = cur->next;)，且寫在了while回圈的內部，

 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/342214.html

標籤：其他

上一篇：18 Linux執行緒

下一篇：再不學ES6你就out啦

反轉單鏈表@Leetcode--鏈表