Odd Even Linked List
Odd Even Linked List
Description
Given a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices. Please note that the even indexed nodes should maintain their relative order. The same goes for the odd indexed nodes.
Note:
- The head of the odd indexed list should point to the head of the even indexed list after rearranging.
Video Explanation
Approach
To solve this problem, we can use two pointers to separate the odd and even indexed nodes while maintaining their relative order. The approach involves:
- Initializing two pointers,
oddandeven, to point to the first node and the second node, respectively. - Using a pointer
even_headto keep track of the head of the even indexed list. - Iterating through the list and rearranging the
nextpointers for odd and even nodes. - At the end of the iteration, connecting the last odd node to the head of the even indexed list.
Solutions
- C++
- Java
- Python
- JavaScript
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head) return nullptr;
ListNode *odd = head, *even = head->next, *evenHead = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
};
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) return null;
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# If the list is empty or has only one node, return it as is
if not head or not head.next:
return head
# Initialize pointers for the odd and even nodes
odd = head
even = head.next
evenHead = even # Store the head of the even list to connect later
# Traverse the list and rearrange odd and even nodes
while even and even.next:
# Link the current odd node to the next odd node
odd.next = even.next
odd = odd.next # Move the odd pointer forward
# Link the current even node to the next even node
even.next = odd.next
even = even.next # Move the even pointer forward
# Connect the last odd node to the head of the even list
odd.next = evenHead
return head
var oddEvenList = function(head) {
if (!head) return null;
let odd = head, even = head.next, evenHead = even;
while (even && even.next) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
};
Track Your Progress
Done with this topic? Mark it as complete to track your progress.
💬 Discuss this page
Have a question or spot something confusing in "Odd Even Linked List"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.