How to Solve Odd Even Linked List
Odd Even Linked List Introduction
Odd Even Linked List Introduction
The Odd Even Linked List problem asks us to group all the nodes with odd indices together followed by the nodes with even indices and return the reordered list. This problem can be solved with a simple approach by separating the odd and even nodes into two groups and then merging these two groups to obtain the final reordered list while maintaining the relative order of nodes within each group.
Odd Even Linked List Problem
Odd Even Linked List Problem
Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
The first node is considered odd, and the second node is even, and so on.
Note that the relative order inside both the even and odd groups should remain as it was in the input.
Example Inputs and Outputs
Example 1
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
Example 2
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
Odd Even Linked List Solutions
Odd Even Linked List Solutions
To reorder the given linked list based on odd and even indices, we can follow a simple approach. We'll divide the linked list into two separate groups: one for nodes with odd indices and one for nodes with even indices. Then, we'll merge these two groups to obtain the final reordered list while maintaining the relative order of nodes within each group. We'll start by initializing two pointers: one for odd nodes and one for even nodes. Initially, the odd pointer will point to the head of the linked list, and the even pointer will point to the next node. We'll also keep track of the head of the even list to connect it later. Next, we'll iterate through the linked list, advancing the odd pointer by two steps and the even pointer by two steps in each iteration. This will separate the nodes into odd and even group while keeping their original order.
Finally, we'll merge the even list after the odd list by linking the last node of the odd group to the head of the even group. This will connect the two groups and give us the desired reordered list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head or not head.next:
return head
odd_head = head
even_head = head.next
odd = odd_head
even = even_head
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return odd_head
# Test case 1
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
head1.next.next.next.next = ListNode(5)
result1 = oddEvenList(head1)
# Expected output: 1 -> 3 -> 5 -> 2 -> 4
current = result1
while current:
print(current.val, end=" -> ")
current = current.next
print("None")1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6def oddEvenList(head):
7 if not head or not head.next:
8 return head
9
10 odd_head = head
11 even_head = head.next
12 odd = odd_head
13 even = even_head
14
15 while even and even.next:
16 odd.next = even.next
17 odd = odd.next
18 even.next = odd.next
19 even = even.next
20
21 odd.next = even_head
22
23 return odd_head
24
25# Test case 1
26head1 = ListNode(1)
27head1.next = ListNode(2)
28head1.next.next = ListNode(3)
29head1.next.next.next = ListNode(4)
30head1.next.next.next.next = ListNode(5)
31result1 = oddEvenList(head1)
32# Expected output: 1 -> 3 -> 5 -> 2 -> 4
33current = result1
34while current:
35 print(current.val, end=" -> ")
36 current = current.next
37print("None")Time/Space Complexity Analysis
- Time Complexity: O(N), where n is the number of nodes in the linked list.
- Space Complexity: O(1), as we use a constant amount of extra space.
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
