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:

1. 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.
2. 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.
3. 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.
4. If the node is at an even position, add it to the end of the even-node list using the same approach as above.
5. 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;
    }
}