leetcode no.206 Reverse Linked List 心得分享

 其實我一開始就看了討論區的解答，但還是看不出來為什麼可以這樣解，印出所有資料後豁然開朗，所以紀錄一下～

https://leetcode.com/problems/reverse-linked-list/

code:

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode() : val(0), next(nullptr) {}

 *     ListNode(int x) : val(x), next(nullptr) {}

 *     ListNode(int x, ListNode *next) : val(x), next(next) {}

 * };

 */

class Solution {

public:

    //印出listnode所有內容

    void printListNode(ListNode* cur){

        ListNode* tmp=cur;

            while(tmp!=NULL){

                cout<<tmp->val<<" ";

                tmp=tmp->next;

            }

            cout<<endl;

    }

    ListNode* reverseListRecursive(ListNode* cur, ListNode* prev){

            if(cur==NULL){

                return prev;

            }

            printListNode(cur); //12345

            ListNode* newL = cur->next;        

            printListNode(newL); //2345

        

            cur->next=prev;

//主要是這邊看不懂，後來知道cur後面被覆寫了，就像是把ListNode切兩半再丟進去下一個迴圈，分開處理

            printListNode(cur); //1

            cout<<endl;

        

            return reverseListRecursive(newL, cur);

        }

    ListNode* reverseList(ListNode* head) {

        return reverseListRecursive(head,NULL);

    }

};

stdout:

1 2 3 4 5
2 3 4 5
1

2 3 4 5
3 4 5
2 1

3 4 5
4 5
3 2 1

4 5
5
4 3 2 1

5

5 4 3 2 1

結果圖：

感覺recursively有點慢

這邊有個更快的

直接改指標方向這樣～

https://leetcode.com/problems/reverse-linked-list/discuss/1664381/Hc%2B%2B-share-my-code

真的指標學得好，Ｃ＋＋沒煩腦

參考資料：

http://alrightchiu.github.io/SecondRound/linked-list-xin-zeng-zi-liao-shan-chu-zi-liao-fan-zhuan.html

https://www.geeksforgeeks.org/print-nodes-of-linked-list-at-given-indexes/