LeetCode 206——チェーンテーブルを反転


単一チェーンテーブルを反転するには反復法と再帰法の2種類がある.
1.反復法
  • 反復法は、チェーンテーブルを前後に巡回し、3つのポインタがそれぞれ隣接する3つのノードを指し、最初の2つのノードを反転させる、すなわち、2番目のノードが1番目のノードを指すように定義する.次にポインタを順番に後ろに移動し、2番目のノードが空になるまで終了し、チェーンテーブルのヘッダーを処理すればよい.
  • /**
     * 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 || head->next == NULL)     //          ,       
            {
                return head;            
            }
            else                                        //        
            {
                ListNode * p1 = head;                   //      
                ListNode * p2 = p1->next;               //      
                ListNode * p3 = p2->next;               //      
    
                while (p2)                              //        ,   ,  
                {
                    p3 = p2->next;
                    p2->next = p1;                      //             ,    
                    p1 = p2;                            //         
                    p2 = p3;                            //         
                }
                
                head->next = NULL;          //                      NULL
                head = p1;                  //               
                return head;
            }
        }
    };

    2.再帰法
  • ベースライン条件:空のチェーンまたは1つのノードのみが、直接ヘッダポインタ
  • に戻る.
  • 再帰条件:再帰呼び出し、サブチェーンテーブル反転後のヘッダポインタ
  • を返す.
    Solution {
    public:
        ListNode* reverseList(ListNode* head) {
        
            if (head == NULL || head->next == NULL)     //          ,       
            {
                return head;            
            }
    
            else                                        //        
            {
                ListNode *new_head = reverseList(head->next); //               
                
                // head->next               
                
                //             
                head->next->next = head;
                head->next = NULL;
                
                return new_head;
            }
        }
    };

    もっと素晴らしいものを手に入れて、「seniusen」に注目してください!