पायथन में लिंक्ड लिस्ट को आगे-पीछे से वैकल्पिक नोड्स लेकर पुनर्व्यवस्थित करने का प्रोग्राम

एक सिंगली लिंक्ड लिस्ट दी गई है। इसे पुनर्व्यवस्थित करें ताकि क्रम हो: अंतिम नोड, पहला नोड, अंतिम से दूसरा, दूसरा, आदि।

उदाहरण

इनपुट: [1,2,3,4,5,6,7,8,9]

आउटपुट: [9, 1, 8, 2, 7, 3, 6, 4, 5]

एल्गोरिदम

1. लिंक्ड लिस्ट को पार करके सभी मानों को सूची vals में संग्रहीत करें।
2. फिर से हेड से शुरू करें। vals से वैकल्पिक रूप से अंतिम और पहला तत्व लेकर नोड्स के मान अपडेट करें:
   • पहले अंतिम तत्व (pop()) लें और वर्तमान नोड में डालें।
   • अगले नोड पर जाएं।
   • फिर पहला तत्व (pop(0)) लें और डालें।
   • दोहराएं जब तक vals खाली न हो जाए।
3. हेड वापस करें।

पायथन कार्यान्वयन

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def print_list(head):
    ptr = head
    print('[', end="")
    while ptr:
        print(ptr.val, end=", ")
        ptr = ptr.next
    print(']')

class Solution:
    def solve(self, node):
        c = node
        vals = []
        # सभी मान इकट्ठा करें
        while c:
            vals.append(c.val)
            c = c.next
        
        c = node
        # वैकल्पिक रूप से भरें
        while c and vals:
            c.val = vals.pop()      # अंतिम
            c = c.next
            if c is None:
                break
            c.val = vals.pop(0)     # पहला
            c = c.next
        return node

# परीक्षण
ob = Solution()
head = make_list([1,2,3,4,5,6,7,8,9])
print_list(ob.solve(head))
# आउटपुट: [9, 1, 8, 2, 7, 3, 6, 4, 5, ]

समय जटिलता

• O(n²) क्योंकि pop(0) O(n) है।
• अनुकूलन: दो पॉइंटर (बाएं/दाएं) का उपयोग करके O(n) समय, O(n) स्थान।

अनुकूलित संस्करण (O(n) समय)

def solve_optimized(self, node):
    vals = []
    c = node
    while c:
        vals.append(c.val)
        c = c.next
    
    left, right = 0, len(vals) - 1
    c = node
    toggle = True
    while c and left <= right:
        c.val = vals[right] if toggle else vals[left]
        if toggle:
            right -= 1
        else:
            left += 1
        toggle = not toggle
        c = c.next
    return node