leetcode-JZ24

問題面
関数を定義し、チェーンテーブルのヘッダノードを入力し、チェーンテーブルを反転し、反転後のチェーンテーブルのヘッダノードを出力します.
例:

  : 1->2->3->4->5->NULL
  : 5->4->3->2->1->NULL

制限:

0 <=      <= 5000

原題リンク
ぶんせき
第一の方法
チェーンテーブルを繰り返し、変数を格納し、逆に新しいチェーンテーブルを作成します.
この方法は簡単でvectorも特定のサイズの配列も定義できます.ただし、チェーンテーブルを2回遍歴したのと同じなので、チェーンテーブル内のすべての遍歴を格納する必要があります.
時間複雑度:O(n)
空間複雑度:O(n)
第2の方法(推奨)
チェーンテーブルを1回だけ巡って、回っているうちに、ポインタの方向を変えます.
チェーンテーブルの最初のノードのnext値をNULLにしなければならないという漏れやすい点があります.そうしないと、犬が自分のしっぽを噛んで回転するように、チェーンテーブルは無限に長くなります.
時間複雑度:O(n)
空間複雑度:O(1)
ソースコード(注釈部分が構想)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //  
        if(head==NULL){
            return head;
        }
        
        ListNode* now = head->next;
        ListNode* pre = head;
        ListNode* later = head;
        //       ，             
        pre->next = NULL;
        
        while(now != NULL){
            later = now->next;
            //      
            now->next = pre;
            
            pre = now;
            now = later;
            
        }
        //  now     NULL
        return pre;
    }
    
};