Əlaqəli Siyahıda Düyünlərin dəyişdirilməsi Leetcode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Bloomberg Facebook microsoftBaxılıb 17

Problem bəyanat

Əlaqəli Siyahıda Düyünlərin dəyişdirilməsi Leetcode Həlli – Sizə verilir head əlaqəli siyahı və tam ədəd k.Qayıt başı əlaqəli siyahı sonra dəyişdirmə dəyərləri kth əvvəldən node və kth sonundan node (siyahı 1 indeksli).

Misal:

Əlaqəli Siyahıda Düyünlərin dəyişdirilməsi Leetcode HəlliPin

Input:

 head = [1,2,3,4,5], k = 2

Çıxış:

 [1,4,3,2,5]

Izahat

Burada əvvəldən ikinci node 2-dirsonundan ikinci node 4-dür (mavi rənglə qeyd olunur), sonra dəyiş-düyüş çıxış [1,4,3,2,5] olur.

Yanaşma

Fikir

Burada sadə fikir 2 göstərici götürmək və onları elə köçürməkdir ki, onlardan biri əvvəldən K-ci qovşağı, digəri isə sondan K-ci qovşağı göstərsin və biz sadəcə olaraq onların hər ikisindəki məlumatları dəyişdirə bilək. .

İndi iki göstəricini müvafiq mövqelərinə necə köçürmək olar.

  1. K-ci node üçün başlanğıcdan – Biz sadəcə baş göstəricini (k-1) dəfə irəli aparırıq ki, o, başlanğıcdan K-ci qovşağı göstərsin.
  2. Sondan K-ci node üçün – Burada bir az iş görməliyik, lakin bu asandır, biz əvvəlcə müvəqqəti göstərici götürüb onu k yer irəli aparırıq və indi nəticəni saxlamaq istədiyimiz göstəricini götürürük. İndi biz müvəqqəti göstəricini və nəticə göstəricisini eyni vaxtda müvəqqəti göstərici NULL olana qədər hərəkət etdiririk. Beləliklə, nəticə göstəricisi sonuncudan K-ci qovşağı göstərəcək.
Əlaqəli Siyahıda Düyünlərin dəyişdirilməsi Leetcode HəlliPin

Kodu

C ++ kodu

class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        
        ListNode* tmp = head;
        int ct = k;
        ListNode* res1 = head;
        ListNode* res2 = head;
        while(ct--){
            res1 = tmp;
            tmp = tmp->next;
        }
        // moving temporary pointer k times and the Kth node from the beginning pointer is moved (k-1) times.
        while(tmp!=NULL){
            tmp = tmp->next;
            res2 = res2->next;
        }
        // moving the temporary and res2 pointer simultaneously.
        swap(res1->val,res2->val);
        return head;
    }
};

Java kodu

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode tmp = head;
        int ct = k;
        ListNode res1 = head;
        ListNode res2 = head;
        while(ct>0){
            res1 = tmp;
            tmp = tmp.next;
            ct--;
        }
        // moving temporary pointer k times and the Kth node from the beginning pointer is moved (k-1) times.
        while(tmp!=null){
            tmp = tmp.next;
            res2 = res2.next;
        }
        // moving the temporary and res2 pointer simultaneously.
        
        int temp = res1.val;
        res1.val = res2.val;
        res2.val = temp;
        return head;
    }
}

Əlaqəli Siyahıda Düyünlərin dəyişdirilməsi üçün Mürəkkəblik Təhlili Leetcode Həll

Zamanın mürəkkəbliyi

Hərəkət etdiyimiz kimi k dəfə birinci döngədə və (nk) dəfə ikinci dövrədə ümumi zaman mürəkkəbliyidir O (n).

Kosmik Mürəkkəblik

Biz heç bir əlavə yer istifadə etmədiyimiz üçün fəzanın mürəkkəbliyi O(1)-dir. Bunu etmək üçün İki Göstəricidən istifadə edirik O(1).

Translate »