Odd Even Linked List

Problem:

Given the head of a linked list , reorder the linked list so that the elements in odd indices are grouped together followed by the elements in event indices.

The first index is assumed to be 1 (odd) and the second index even and so on.

For example,

For the below input:

1 -> 2-> 3-> 4 -> 5 -> 6 -> 7

The output is :

1 -> 3 -> 5 -> 7 ->2 -> 4 ->6

Find a solution in O(n) time complexity and O(1) space complexity.

Try out the solution here:

https://leetcode.com/problems/odd-even-linked-list/

Solution:

The solution is intuitive.

Just make each odd element point to the next to next element starting from the first element which is odd.

And point each even element to the next element of the next odd element starting from the second element which is even.

To implement make use of two pointers:

The odd pointer which is used to navigate the odd elements.

The even pointer which is used to navigate the even elements.

Use a even head pointer to point to the first even element.

We already have the input head pointer which points to the first odd element.

So in total we need four pointers , two pointing to the start of the odd and even lists and two for navigating odd and even elements.

we will iterate through the linked list as long as the next element of the current odd and current even elements are not null.

Once we find out the even elements , we point the next pointer of the last odd element to the even head.

Here is the code:

/**
 * 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) return head;
        
        
        ListNode odd =head;
   
        ListNode evenhead = odd.next;
        
        ListNode even = evenhead;
        
        
        while(odd != null && odd.next != null && even.next != null){
            
            
             
            
            odd.next = odd.next.next;
            
            odd = odd.next;
            
            
            even.next = odd.next;
            
            even = even.next;
            
            
        }
        
        
      odd.next = evenhead;
        
        return head;
    }
}

Time complexity is O(n) since we make a single pass.

Space complexity is O(1) since we don’t use any extra space in proportion to the input.

That’s it!