«Խնդիրի հայտարարություն.

You are given the head of a linked list, and an integer k.
Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

Օրինակ՝

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

Լուծում:

Մեր հիմնական խնդիրն էորոշել այն հանգույցների գտնվելու վայրը, որոնց արժեքները պետք է փոխվեն:

Այս խնդիրը լուծելու համար մենք պատրաստվում ենք 2 կետանոց մոտեցում ցուցաբերել, այն, ինչ պետք է նկատի ունենանք, այն է, որ մենք պետք է պահպանենք այս երկու ցուցիչների միջև եղած բացը:

Հեռավորությունը պետք է ընտրվի այնպես, որ.

  • երբ դանդաղ գտնվում է գլխում, արագ մատնանշում է առաջին հանգույցը փոխարինելու համար
  • երբ արագ վերջում է, դանդաղ մատնանշում է երկրորդ հանգույցը փոխանակման համար

Այսպիսով, հետևելով այս մոտեցմանը, մենք կարող ենք լուծել այս խնդիրը O(n) ժամանակում և O(1) տարածության մեջ:

Իրականացում:

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode first=head,second=head,fast=head,slow=head;        
        while(k!=1){
            fast = fast.next;
            k--;
        }
        first = fast;
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        second = slow;
        k = slow.val;
        slow.val = first.val;
        first.val = k;
        return head;
    }
}

Հղումներ՝
-Leetcode Discussion

Միանալու և համագործակցելու համար զանգահարեք ինձ՝
LinkedIn
Twitter
GitHub