Solution For Odd Even Linked List
The Odd Even Linked List problem on LeetCode requires us to modify a given singly linked list such that all odd-indexed nodes come before the even-indexed nodes. Specifically, the modified list should have all the nodes at odd positions arranged first, followed by all the nodes at even positions. The nodes are numbered 1, 2, 3, …, n, where n is the length of the list.
Here’s a detailed solution to the problem:
- Initialize two variables, one to keep track of the odd-node list (oddHead) and the other to keep track of the even-node list (evenHead) as null.
- Traverse through the given linked list (head) and for each node check if it is at an odd or even position using the node number.
- If the node is at an odd position, add it to the end of the odd-node list by checking if oddHead is null. If it is null, set oddHead to the current node. Otherwise, link the current node to the end of the odd-node list.
- If the node is at an even position, add it to the end of the even-node list using the same approach as above.
- After all the nodes have been traversed, link the end of the odd-node list to the start of the even-node list by checking if oddHead is null. If it is null, return evenHead. Otherwise, link the last node of the odd-node list to the first node of the even-node list and return oddHead.
Here’s the implementation of the solution in Python:
“`python
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
oddHead = oddTail = None
evenHead = evenTail = None
count = 1
while head:
if count % 2 == 1:
if not oddHead:
oddHead = oddTail = head
else:
oddTail.next = head
oddTail = oddTail.next
else:
if not evenHead:
evenHead = evenTail = head
else:
evenTail.next = head
evenTail = evenTail.next
head = head.next
count += 1
oddTail.next = evenHead
evenTail.next = None
return oddHead
“`
In the above code, we first check if the given linked list has less than two nodes and if it does, we return it as is. We then initialize variables oddHead and evenHead to null. We also keep track of the tail nodes of both the odd and even lists, initialized to None. A variable count is also initialized to keep track of the node number, starting from 1. We traverse the given linked list using a while loop, keeping track of the node position using count.
If the current node is at an odd position, we add it to the odd list by checking if oddHead is null. If it is null, we set it to the current node and update the oddTail. Otherwise, we link the current node to the end of the odd list and update the oddTail. If the current node is at an even position, we add it to the even list in the same way.
After traversing all the nodes, we link the end of the odd list to the start of the even list by setting oddTail.next to evenHead. We also set evenTail.next to null to terminate the even list. Finally, we return oddHead as the modified linked list.
Step by Step Implementation For Odd Even Linked List
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode oddEvenList(ListNode head) { if(head == null || head.next == null) return head; ListNode odd = head, even = head.next, evenHead = even; while(even != null && even.next != null){ odd.next = odd.next.next; even.next = even.next.next; odd = 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: ListNode) -> ListNode: if head is None: return None odd = head even = head.next evenHead = even while even is not None and even.next is not None: odd.next = even.next odd = odd.next even.next = odd.next even = even.next odd.next = evenHead return head
var oddEvenList = function(head) { if(head === null) return null; let odd = head; let even = head.next; let 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. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* oddEvenList(ListNode* head) { if(head == nullptr || head->next == nullptr) return head; ListNode* odd = head; ListNode* even = head->next; ListNode* evenHead = even; while(even != nullptr && even->next != nullptr) { odd->next = odd->next->next; odd = odd->next; even->next = even->next->next; even = even->next; } odd->next = evenHead; return head; } };
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode OddEvenList(ListNode head) { //edge case - if head is null or there is only 1 node in the list if(head == null || head.next == null){ return head; } //set up 2 pointers - one for the head of the odd list and one for the head of the even list ListNode odd = head; ListNode even = head.next; //set up a pointer for the head of the even list so we can connect the odd list to the end of the even list later ListNode evenHead = even; //while there are still nodes in the list while(even != null && even.next != null){ //set odd.next to the next odd node odd.next = even.next; //increment odd to the next odd node odd = odd.next; //set even.next to the next even node even.next = odd.next; //increment even to the next even node even = even.next; } //set odd.next to the head of the even list so the odd list is now connected to the end of the even list odd.next = evenHead; //return the head of the odd list return head; } }