[LeetCode]206. Reverse Linked List(反轉單連結清單)

206. Reverse Linked List

Reverse a singly linked list.

反向單連結清單。

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

提示：

可以疊代或遞歸地颠倒連結清單

思路1：

• 現将連結清單變成環，每次都将原第一個結點之後的那個結點放在新的表頭後面，最後斷開環。
• 比如1,2,3,4,5 變成1,2,3,4,5->1(環)
• 第一次：把第一個結點1後邊的結點2放到新表頭後面，變成2,1,3,4,5 ->2(環)
• 第二次：把第一個結點1後邊的結點3放到新表頭後面，變成3,2,1,4,5 ->3(環)
• 4,3,2,1,5 ->4(環)

• 5,4,3,2,1 ->5(環)

  代碼如下：

ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* res;
        ListNode* first;
        ListNode* temp;
        res = new ListNode(-);
        res->next = head; //将單連結清單變成環
        first = head;//指向原連結清單的頭結點
        while(first->next != nullptr){
            temp = first->next;//指向即将處理的點
            first->next = temp->next;
            temp->next = res->next;
            res->next = temp;
        }
        head = res->next;
        res->next = nullptr;
        return head;
    }
           

思路2：

• 參考了網上别人寫的方法，點選檢視

代碼如下：

ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* p;
        ListNode* q;
        ListNode* r;
        p = head;
        q = head->next;
        head->next = nullptr;//舊的頭指針是新的尾指針 指向NULL
        while(q){
            r = q->next;//用來儲存下一步要處理的指針
            q->next = p;//p q 交替處理 進行反轉單連結清單
            p = q;
            q = r;
        }
        head = p;//最後的q必定指向NULL，p就成了新連結清單的頭指針
        return head;
    }
           

思路3：

• 遞歸，參考連結
• 現在需要把A->B->C->D進行反轉，
• 可以先假設B->C->D已經反轉好，已經成為了D->C->B,那麼接下來要做的事情就是将D->C->B看成一個整體，讓這個整體的next指向A，是以問題轉化了反轉B->C->D。那麼，
• 可以先假設C->D已經反轉好，已經成為了D->C,那麼接下來要做的事情就是将D->C看成一個整體，讓這個整體的next指向B，是以問題轉化了反轉C->D。那麼，
• 可以先假設D(其實是D->NULL)已經反轉好，已經成為了D(其實是head->D),那麼接下來要做的事情就是将D(其實是head->D)看成一個整體，讓這個整體的next指向C，是以問題轉化了反轉D。

代碼如下:

ListNode* reverseList(ListNode* head) {
        if (!head || !(head -> next)) return head;
        ListNode* node = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return node; 
    }