Tək Cüt Əlaqəli Siyahı Leetcode Həlli

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Tək-Cüt Əlaqəli Siyahı LeetCode Həlli – “Tək-Cüt Bağlantılı Siyahı” tək-tək boş olmayan bir verildiyini bildirir əlaqəli siyahı. Biz tək indeksli bütün qovşaqları, ardınca isə cüt indeksli qovşaqları qruplaşdırıb yenidən sıralanmış siyahını qaytarmalıyıq.

Qeyd edək ki, həm cüt, həm də tək qruplar daxilində nisbi sıra girişdə olduğu kimi qalmalıdır.

Misal:

Pin

Input:  head = [1,2,3,4,5]

Output: [1,3,5,2,4]

Explanation:

• Tək indekslərdə mövcud olan qovşaqlar bunlardır: [1, 3, 5].
• Cüt indekslərdə mövcud olan qovşaqlar bunlardır: [2, 4].
• Yuxarıdakı iki dəsti qruplaşdırmaq haqqında: [1, 3, 5, 2, 4].

Input:  head = [2,1,3,5,6,4,7]

Output: [2,3,6,7,1,5,4]

Explanation:

• Tək indekslərdə mövcud olan qovşaqlar bunlardır: [2, 3, 6, 7].
• Cüt indekslərdə mövcud olan qovşaqlar bunlardır: [1, 5, 4].
• Yuxarıdakı iki dəsti qruplaşdırmaq haqqında: [2, 3, 6, 7, 1, 5, 4].

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas ideya sadə traversiyadan istifadə etməkdir əlaqəli siyahılar.
2. Əlaqədar siyahıdan keçin və dəyişəni saxlamaq cari qovşağın tək indeksdə və ya cüt indeksdə olmasını izləyir.
3. Cari qovşaq tək indeksdədirsə, onu tək əlaqəli siyahının növbəti node kimi təyin edin.
4. Cari qovşaq cüt indeksdədirsə, onu cüt əlaqəli siyahının növbəti node kimi təyin edin.
5. Nəhayət, cüt əlaqəli siyahının baş qovşağı tək əlaqəli siyahının sonundakı növbəti qovşaqdır, buna görə də tək və cüt indeksləri birlikdə qruplaşdırır.
6. Cavabımız olaraq yeni qruplaşdırılmış əlaqəli siyahının başını qaytarın.

Kodu

Tək-Cüt Əlaqəli Siyahı Leetcode C++ Həlli:

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode* dummy_odd = new ListNode(-1);
        ListNode* dummy_even = new ListNode(-1);
        
        ListNode* odd = dummy_odd;
        ListNode* even = dummy_even;
        
        int n = 0;
        ListNode* curr = head;
        
        while(curr != nullptr){
            n++;
            
            if(n % 2 == 1){
                odd->next = curr;
                odd = odd->next;
            }
            else{
                even->next = curr;
                even = even->next;
            }
            
            curr = curr->next;
        }
        
        even->next = nullptr;
        odd->next = dummy_even->next;
        
        return dummy_odd->next;
    }
};

Tək-Cüt Əlaqəli Siyahı Leetcode Java Həlli:

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode dummy_odd = new ListNode(-1);
        ListNode dummy_even = new ListNode(-1);
        
        ListNode odd = dummy_odd;
        ListNode even = dummy_even;
        
        int n = 0;
        ListNode curr = head;
        
        while(curr != null){
            n++;
            
            if(n % 2 == 1){
                odd.next = curr;
                odd = odd.next;
            }
            else{
                even.next = curr;
                even = even.next;
            }
            
            curr = curr.next;
        }
        
        even.next = null;
        odd.next = dummy_even.next;
        
        return dummy_odd.next;
    }
}

Tək-Cüt Əlaqəli Siyahı Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (N) çünki biz bütün əlaqəli siyahıdan bir dəfə keçdik.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz daimi əlavə yerdən istifadə edirik. Tək indekslərdə olan qovşaqları qruplaşdırmaq üçün iki dummy qovşaq yaratdıq, sonra cüt indekslərdə olan qovşaqlar.