🔥 Rearrange Linked List: Odd-Even Index Grouping in O(n) Time & O(1) Space! 🚀 #Python #LeetCode75

🔹 Problem Overview:

Given the head of a singly linked list, the task is to group all odd-indexed nodes together followed by even-indexed nodes, while maintaining their relative order. The first node is considered odd, the second is even, and so on. The solution must be optimized to run in O(n) time complexity and O(1) extra space complexity.

🔹 Approach & Explanation:

Step 1: Handle Edge Cases

✅ If the list is empty (head is None) or has only one node (head.next is None), return head immediately, as reordering is unnecessary.

Step 2: Define Pointers for Odd and Even Nodes

📌 Initialize two pointers:

odd = head → Tracks odd-indexed nodes
even = head.next → Tracks even-indexed nodes
even_head = even → Stores the start of the even nodes to reconnect later

Step 3: Rearrange the Nodes

🔄 Traverse the list while even and even.next exist:

1️⃣ Re-link odd nodes → Move odd.next to even.next (next odd node).
2️⃣ Move odd pointer → odd = odd.next.
3️⃣ Re-link even nodes → Move even.next to odd.next (next even node).
4️⃣ Move even pointer → even = even.next.

Step 4: Connect the Odd and Even Lists

📌 Once all odd and even nodes are separated, connect the last odd node to the head of the even list (even_head).

Step 5: Return the Reordered Linked List

🚀 The modified linked list is now structured as all odd-indexed nodes first, followed by even-indexed nodes, while keeping their original relative order.

🔹 Time & Space Complexity Analysis

✅ O(n) Time Complexity: We traverse the linked list only once.
✅ O(1) Space Complexity: We only modify pointers without extra data structures.

🔹 Example Walkthrough

Example 1:

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

Processing:

Odd Group: [1,3,5]

Even Group: [2,4]

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

Example 2:

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

Processing:

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

💡 This solution is efficient, follows the problem constraints, and maintains the required order!

🔗 Try it out on LeetCode now! 💻🔥

#DataStructures #Algorithms #Coding #PythonProgramming #LeetCodeChallenge

Видео 🔥 Rearrange Linked List: Odd-Even Index Grouping in O(n) Time & O(1) Space! 🚀 #Python #LeetCode75 канала CodeVisium