データ構造のチェーンテーブル練習問題

これらの練習はすべてボタンの中の本題で、チェーン時計についてもっと理解しやすいです.
1、チェーンテーブルの所与の値valに等しいすべてのノードを削除する

void SListRemoveAll(SList *s, SLDataType v){
    if (s->first == NULL){
        return;
    }
    if(s->first->value == v){
        Node *next = s->first;
        s->first = s->first->next;
        free(s->first);
    }
    else{
        Node *c = s->first;
        while(c->next != NULL){
            if(c->next->value == v){
                Node *next = c->next;
                c->next = c->next->next;
                free(c->next);
            }
            else{
                c = c->next;
            }
        }
    }
}

2、単一チェーンテーブルを反転します.

void SListReverse(SList *head){
    Node *result = NULL;
    Node *c = head;
    
    while(c != NULL){
        Node *next = c->next;
        
        c->next = result;
        result = c;
        
        c = next;
    }
    return result;
}

3、ヘッドノードheadを有する非空の単一チェーンテーブルを与え、チェーンテーブルの中間ノードを返す.中間ノードが2つある場合は、2番目の中間ノードを返します.

Node* middleNode(SList *head){
    if(head == NULL){
        return NULL;
    }//         
    Node *fast = head;
    Node *slow = head;
    while(1){
        fast = fast->next;
        if(fast == NULL){
            break;
        }
        slow = slow->next;
        fast = fast->next;
        if(fast == NULL){
            break;
        }
    }
    return slow;
}

4、チェーンテーブルを入力し、そのチェーンテーブルの最後からk番目のノードを出力する.

Node *FindKthToTail(Node *head, unsigned int k){
    Node *front = head;
    Node *back = head;
    //      k 
    int i;
    for(i = 0;i < k && front != NULL;i++){
        front = front->next;
    }
    if(i < k){
        return NULL;
    }
    while(front != NULL){
        front = front->next;
        back = back->next;
    }
    return back;
}

5、2つの順序付きチェーンテーブルを1つの新しい順序付きチェーンテーブルに結合して返します.新しいチェーンテーブルは、指定された2つのチェーンテーブルのすべてのノードを接合することによって構成されます.新しいチェーンテーブルも秩序があります.

Node* mergeTwoList(SList *c1, SList *c2){
    
    struct SList *c1 = l1;
    struct SList *c2 = l2;
    struct SList *result = NULL;
    struct SList *last = NULL;
    
    if(l1 == NULL){
        return l2;
    }
    if(l2 == NULL){
        return l1;
    }
    while(l1 != NULL && l2 != NULL){
        if(l1->value <= l2->value){
            if(result == NULL){
                result = last = l1;
            }
            else{
                last->next = last;
                last = l1;
            }
            l1 = l1->next;
        }
        else{
             if(result == NULL){
                result = last = l2;
            }
            else{
                last->next = last;
                last = l2;
            }
            l2 = l2->next;
        }
    }
    //           ，                
    if(l1 != NULL){
        last->next = l1;
    }
    if(l2 != NULL){
        last->next = l2;
    }
    
    return result;
}

6、コードを作成し、所与の値xを基準としてチェーンテーブルを2つの部分に分割し、x未満のすべてのノードはx以上のノードの前に並ぶ.

Node *partition(SList* head, int x){
    
    SList *small;
    SList *big;
    SList *lastsmall;
    SList *lastbig;
    
    SList *node = head;
    while(node != NULL){
        if(node->value < x){
            if(small == NULL){
                small = smalllast =node;
            }
            else{
                lastsmall->next = node;
                lastsmall = node; // lastsmall          ，   node           ，  node                 
            }
        }
        else{
            if(big == NULL){
            big = lastbig =node;
            }
            else{
                lastbig->next = node;
                lastbig = node;
            }
        }
        node = node->next;
    }
    if(lastsmall != NULL){
        //   x      ，        big  
        lastsmall->next = big;
    }
    if(lastbig != NULL){
        //   x      ，        NULL
        lastbig->next = NULL;
    }
    if(lastsmall != NULL){
        return small;
    }
    else{
        return big;
    }
}

7、並べ替えられたチェーンテーブルに重複するノードが存在する場合、そのチェーンテーブルの重複するノードを削除してください.重複するノードは保持されず、チェーンテーブルヘッダポインタに戻ります.

Node *deleteDuplication(SList* head){
    if(head == NULL){
        return NULL;
    }
    SList *fake = (Node*)malloc(sizeof(Node));//        
    fake->next = head;
    
    SList *prev = fake;
    SList *p1 = head;
    SList *p2 = head->next;
    while(p2 != NULL){//      ，  p2      ，        
    //    ，     ，     ，              
    if(p1->val != p2->val){
        prev = p1;
        p1 = p2;
        p2 = p2->next;
    }
    else{
        while(p2 != NULL && p1->val == p2->val){
            p2 = p2->next;
        }
        SList *cur = p1;
        while(cur != p2){
            SList *next = cur->next;
            free(cur);
            cur = next;
        }
        prev->next = p2;//      ，            
        p1 = p2;
        if(p2 != NULL){
            p2 = p2->next;
        }
    }
	}
    head = fake->next;
    //prev           ，  fake
    free(fake);
    return head;
}

8、チェーンテーブルについて、時間的複雑度がO(n)、余分な空間的複雑度がO(1)のアルゴリズムを設計し、それが回文構造であるかどうかを判断してください.

1->2->2->1

考えはよく理解できる
1、中間ノードを見つける
2、中間接点からチェーンテーブル全体を後ろに逆転
3、頭の接点と逆転配列を比較する

ListNode *middleNode(ListNode *head){
    if(head == NULL){
        return NULL;
    }
    ListNode *slow = head;
    ListNode *fast = head;
    
    while(1){
        fast = fast->next;
        if(fast == NULL){
            break;
        }
        slow = slow->next;
        fast = fast->next;
        if(fast == NULL){
            break;
        }
    }
    return slow;
}

ListNode *reverlist(ListNode *head){
    if(head == NULL){
        return NULL;
    }
    ListNode *result = NULL;
    ListNode *cur = head;
    
    while(cur != NULL){
        ListNode *next = cur->next;
        
        cur->next = result;
        result = cur;
        
        cur = next;
    }
    return result;
}

bool chkPalindrome(ListNode* A){
    ListNode *middle = middleNode(A);
    ListNode *r = reverselist(middle->next);
    
    ListNode *n1 = A, *n2 = r;
    while(n1 != NULL && n2 != NULL){
        if(n1->val != n2->val){
            return false;
        }
        n1 = n1->next;
        n2 = n2->next;
    }
    return true;
}