プログラミング練習:チェーンテーブル練習問題(上)

(1)タイトル:2つのチェーンテーブルを入力し、最初の共通ノードを見つけます.
考え方:1)チェーンテーブル1の長さを算出する;2)チェーンテーブル2の長さを算出する.3)チェーンテーブル1とチェーンテーブル2の長さ差difを算出する.4)長鎖表はdifステップを先に進み,2つの鎖表が2つの鎖表のノードが初めて等しくなるまで2つの鎖表が一緒に歩くと,ポインタ位置が求められる.
コード実装:

class Solution {
public:
   ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *p1=pHead1;
        ListNode *p2=pHead2;
        int len1=0,len2=0,dif=0;
        while(p1!=NULL){
            p1=p1->next;
            len1++;
        }
        while(p2!=NULL){
            p2=p2->next;
            len2++;
        }
        if(len1>len2){
            dif=len1-len2;
            p1=pHead1;
            p2=pHead2;
        }
        else{
            dif=len2-len1;
            p1=pHead2;
            p2=pHead1;
        }
        for(int i=0;inext;
        }
        while(p1!=NULL && p2!=NULL){
            if(p1==p2)
                break;
            p1=p1->next;
            p2=p2->next;
        }
        return p1;
    }
};

(2)タイトル:チェーンテーブルで重複するノードを削除する
コード実装:

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {

       if (pHead==NULL)
            return NULL;
        if (pHead!=NULL && pHead->next==NULL)
            return pHead;

        ListNode* current;

        if ( pHead->next->val==pHead->val){
            current=pHead->next->next;
            while (current != NULL && current->val==pHead->val)
                current=current->next;
            return deleteDuplication(current);                     
        }   
        else {
            current=pHead->next;
            pHead->next=deleteDuplication(current);
            return pHead;
        }    
    }
};

(3)タイトル:sort-list:Sort a linked list in O(n log n)time using constant space complexity.
考え方:(1)速慢指針法チェーンテーブルを中間からl 1,l 2の2つの部分(2)左右の2つの部分のチェーンテーブルをそれぞれ再帰的に並べ替える(3)2つのサブチェーンテーブルを統合する
コード実装:

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode* p = head;
        ListNode* q = head->next;
        while(q && q->next)
        {
            p = p->next;
            q = q->next->next;
        }

        ListNode* l1 = sortList(p->next);
        p->next = NULL;
        ListNode* l2 = sortList(head);
        return Merge(l1,l2);
    }
        ListNode* Merge(ListNode* l1,ListNode* l2)
        {
            ListNode L(0);
            ListNode* p = &L;
            while(l1&&l2)
            {
                if(l1->val < l2->val)
                {
                    p->next = l1;
                    l1=l1->next;
                }
                else
                {
                    p->next = l2;
                    l2=l2->next;
                }
                p = p -> next;
            }
            if(l1 != NULL)
                p->next = l1;
            if(l2 != NULL)
                p->next = l2;
            return L.next;
        }
};

(4)タイトル:Given a singly linked list L:L 0→L 1→...→L n-1→L n,reorder it to:L 0→L n→L 1→L n-1→L 2→L n-2→…You must dothis in-place without altering the nodes’values.For example, Given{1,2,3,4}, reorder it to{1,4,2,3}.
考え方:(1)速慢指針法で中間ノードを見つける(2)チェーンテーブルの後半を逆順にする(3)前半と逆順後の後半を合併する
コード実装:

class Solution {
public:
    void reorderList(ListNode *head) {
        if(head == NULL || head->next == NULL || head->next->next == NULL)
            return;

        //       
        ListNode* fast = head;
        ListNode* low = head;
        while(fast->next != NULL && fast->next->next != NULL)
        {
            fast = fast->next->next;
            low = low->next;
        }

        // low       
        fast = low->next;
        low->next = NULL;
        while(fast != NULL){
            ListNode* temp = fast->next;
            fast->next = low->next;
            low->next = fast;
            fast = temp;
        }

        //  low        
        ListNode* p = head;
        ListNode* q = low->next;
        while(p != NULL && q != NULL){
            low->next = q->next;
            q->next = p->next;
            p->next = q;
            p = q->next;
            q = low->next;
        }
    }
};

(5)タイトル:Given a linked list and a value x,partition it such that all nodes than x come before nodes greater than or equal to x.You should preserve the original relative order of the nodes in each of the two partions.For example, Given1->4->3->2->5->2and x = 3, return1->2->2->4->3->5..
構想:(1)新しい2つのノードはそれぞれfastとslowで、それぞれ2つのヘッドノードを指します;(2)x値未満のノードはp 1に接続され、x値以上のノードはp 2にリンクされる.(3)最後に2つのチェーンテーブルを接続する.
コード実装:

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if(head == NULL)
            return NULL;
        ListNode* fast = new ListNode(0);
        ListNode* slow = new ListNode(0);
        ListNode* p1 = slow;
        ListNode* p2 = fast;
        ListNode *p = head;
        while(p!=NULL)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }
            p = p->next;
        }
        p2->next = NULL;
        p1->next = fast->next;
        return slow->next;
    }
};