leetcode:チェーンテーブルタイトル2

文書ディレクトリ

160. Intersection of Two Linked Lists(交差チェーンテーブルの交差点)

24. Swap Nodes in Pairs(ペア交換チェーンテーブルノード)

142. Linked List Cycle II(リングの入口を見つける)

445. Add Two Numbers II(2つのチェーンテーブルノード値を加算)

23. Merge k Sorted Lists(k個の並べ替えられたチェーンテーブルをマージ)

160.Intersection of Two Linked Lists(交差チェーンテーブルの交差点)
2つのチェーンテーブルを1つに結合し、例えばチェーンテーブルA、チェーンテーブルBを2つのチェーンテーブルA−>BおよびB−>Aに結合する.

//    ：
//  listB  listA   、 listA   listB   ，    list  
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* a_ptr = headA;
        ListNode* b_ptr = headB;
        
        while( a_ptr != b_ptr)
        {
            if(a_ptr == NULL)
                a_ptr = headB;
            else
                a_ptr = a_ptr->next;
            
            if(b_ptr == NULL)
                b_ptr = headA;
            else
                b_ptr = b_ptr->next;
        }
        return a_ptr;
    }
};

24.Swap Nodes in Pairs(ペア交換チェーンテーブルノード)

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* pre = new ListNode(-1);
        ListNode* pre_next = NULL;
        ListNode* pre_next2 = NULL;
        ListNode* pre_next3 = NULL;
        ListNode* head_pre = pre;
        pre->next = head;
        while(pre->next && pre->next->next)
        {
            pre_next =  pre->next;
            pre_next2 = pre->next->next;
            pre_next3 = pre->next->next->next;
            
            pre_next->next = pre_next3;
            pre_next2->next = pre_next;
            pre->next = pre_next2;
            
            pre = pre->next->next;
            

        }  
        return head_pre->next;
    }
};

142.Linked List Cycle II(リングの入口を見つける)
まず,ループであるか否かをスローポインタで判断し,headポインタとスローポインタの交差点からそれぞれポインタで交差するループの入口推定にチェーンテーブル問題を参照する.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
       if (head == NULL)  return NULL; 
        
        //         
        ListNode *slow_ptr = head;
        ListNode *fast_ptr = head;
        bool bool_loop = false;
        while ( fast_ptr != NULL && fast_ptr->next != NULL && fast_ptr->next->next != NULL)
        {
            fast_ptr = fast_ptr->next->next;
            slow_ptr = slow_ptr->next;
            if ( fast_ptr == slow_ptr )
            {
                bool_loop = true;
                break;
            }
                
        }
        
        if (!bool_loop)
            return NULL;
        
        //        
        ListNode *tmp_ptr = head;
        while ( tmp_ptr != slow_ptr )   //            ，  val       
        {
            tmp_ptr = tmp_ptr->next;
            slow_ptr = slow_ptr->next;
        }
        
        return tmp_ptr;
    }
};

445.Add Two Numbers II(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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;        
        stack s1;          //   stack            
        stack s2;
        while(l1){
            s1.push(l1->val);
            l1 = l1->next;
        }
        while(l2){
            s2.push(l2->val);
            l2 = l2->next;
        } 
        int sum = 0;
        ListNode* res = NULL;
        ListNode* tmp = NULL;
        while(  !s1.empty() || !s2.empty()){
            if(!s1.empty()){
                sum+=s1.top();
                s1.pop();
            }
            if(!s2.empty()){
                sum+=s2.top();
                s2.pop();
            }
            tmp = new ListNode(sum%10);
            tmp->next = res;
            res = tmp;
            sum = sum/10;
        }    
        if(sum > 0){ //           
            tmp = new ListNode(sum);
            tmp->next = res;
            res = tmp;
        }        
        return res;
    }
};

23.Merge k Sorted Lists(k個の並べ替えられたチェーンテーブルをマージ)
優先キューでソート

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        auto cmp = [](ListNode*& cmpa, ListNode*& cmpb)
        {
            return cmpa->val > cmpb->val;
        };
        
        //            head         
        priority_queue, decltype(cmp)> pri_queue(cmp);
        for(auto node : lists)  //               
        {
            if(node) pri_queue.push(node);
        }
        
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while(!pri_queue.empty())
        {
            auto p = pri_queue.top();
            pri_queue.pop();
            cur->next = p;
            cur = cur->next;
            if(cur->next) pri_queue.push(cur->next);  //     next  ，  next        
        }
        return dummy->next;
    }
};