ধরা যাক একটি লিংকড লিস্ট আছে như l1 -> l2 -> l3 -> l4 -> ... -> l(n-1) -> ln। আমরা এই লিস্টকে l1 -> ln -> l2 -> l(n-1) -> ... আকারে রিয়ারেঞ্জ করব। এখানে বাধা হলো, আমরা লিস্ট নোডের মান পরিবর্তন করতে পারব না, শুধু নোডগুলোর লিংক পরিবর্তন করতে পারব। উদাহরণস্বরূপ, যদি লিস্ট হয় [1,2,3,4,5], তবে আউটপুট হবে [1,5,2,4,3]
সমাধানের ধাপগুলো −
reverse নামে একটি মেথড সংজ্ঞা করব যা রিভার্স অপারেশন করবে। এটি নোড head এবং নোড prev নিবে। এটি নিচেরভাবে কাজ করবে −
যদি head null হয়, তবে prev রিটার্ন করব
temp := head-এর next
head-এর next := prev, এবং prev := head
reverse(temp, prev) রিটার্ন করব
রি-অর্ডারিং টাস্কটি নিচের মতো −
যদি head null হয়, তবে null রিটার্ন করব
slow এবং fast নামে দুটি নোড পয়েন্টার সংজ্ঞা করব এবং তাদের head দিয়ে ইনিশিয়ালাইজ করব
যখন fast এবং fast-এর next উভয় null নয়
slow := slow-এর next
fast := fast-এর next-এর next
fast := reverse(slow-এর next)
slow-এর next := null, এবং slow := head
temp1 এবং temp2 নামে দুটি লিস্ট নোড পয়েন্টার সংজ্ঞা করব
যখন fast null নয়
temp1 := slow-এর next, temp2 := fast-এর next
slow-এর next := fast, fast-এর next := temp1
slow := temp1, fast := temp2
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; class ListNode{ public: int val; ListNode *next; ListNode(int data){ val = data; next = NULL; } }; ListNode *make_list(vector<int> v){ ListNode *head = new ListNode(v[0]); for(int i = 1; i<v.size(); i++){ ListNode *ptr = head; while(ptr->next != NULL){ ptr = ptr->next; } ptr->next = new ListNode(v[i]); } return head; } void print_list(ListNode *head){ ListNode *ptr = head; cout << "["; while(ptr){ cout << ptr->val << ", "; ptr = ptr->next; } cout << "]" << endl; } class Solution { public: ListNode* successor = NULL; ListNode* reverse(ListNode* head, ListNode* prev = NULL){ if(!head)return prev; ListNode* temp = head->next; head->next = prev; prev = head; return reverse(temp, prev); } void reorderList(ListNode* head) { if(!head)return; ListNode* slow = head; ListNode* fast = head; while(fast && fast->next){ slow = slow->next; fast = fast->next->next; } fast = reverse(slow->next); slow->next = NULL; slow = head; ListNode *temp1, *temp2; while(fast){ temp1 = slow->next; temp2 = fast->next; slow->next = fast; fast->next = temp1; slow = temp1; fast = temp2; } } }; main(){ vector<int> v = {1,2,3,4,5}; ListNode *h1 = make_list(v); Solution ob; (ob.reorderList(h1)); print_list(h1); }
ইনপুট
[1,2,3,4,5]
আউটপুট
[1, 5, 2, 4, 3, ]
