LeetCode Challenge #328. Odd Even Linked List

Question 30 of 75 - LeetCode Weekly Challenge

Day 66 of 100 Days LeetCode Challenge

LeetCode Challenge #328. Odd Even Linked List

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.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

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]

Constraints:

The number of nodes in the linked list is in the range [0, 10⁴].
-10⁶ <= Node.val <= 10⁶

C++ Video Solution

Java Video Solution

Java Solution

				
					class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null){
            return head ;
        }
        ListNode oddHead = head ;
        ListNode evenHead = head.next ;
        ListNode evenStart = evenHead;

        while(evenHead!=null && evenHead.next!=null){
            oddHead.next = oddHead.next.next;
            evenHead.next = evenHead.next.next;

            oddHead = oddHead.next;
            evenHead = evenHead.next;
        }

        oddHead.next = evenStart;

        return head ;
    }
}

C++ Solution

				
					class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode list1(0),list2(0);
        ListNode* temp1=&list1;
        ListNode* temp2=&list2;

        int index=1;

        while(head)
        {
            if(index%2==1)
            {
                temp1->next=head;
                temp1=temp1->next;
            }
            else
            {
                temp2->next=head;
                temp2=temp2->next;
            }
           index++;
            head=head->next;
        }
        temp1->next=list2.next;
        temp2->next=NULL;
        
        return list1.next;
    }
};

Code Explanation

The purpose of this function is to rearrange the nodes in such a way that all nodes with odd positions appear before nodes with even positions.

Let’s see the step-by-step approach towards the solution:

Two nodes are created, ‘list1’ and ‘list2’ to represent the heads of two separate linked lists: one for odd-positioned nodes and one for even-positioned nodes.
Two pointers, ‘temp1’ and ‘temp2’ are initialised to point to the respective nodes ‘list1’ and ‘list2’.
An index is initiated which stores one initially. So. A while loop is used to iterate through the original linked list (‘head’)

if the index is odd then (temp1-> next=head ) it appends the current node to the list of odd-positioned nodes. After appending the current node to the list of odd-positioned nodes, ‘temp1’ is updated to point to the last node and this step is crucial for maintaining the correct structure of the list.
- if the index is even then the temp2 will point towards its next. (temp2=temp2->next)

Now, we have to append list2 before list1 avoiding zero.
So after iterating through the original list, the next pointer of the last node in the list of odd-positioned nodes ‘temp1’ is set to the head of the list of even-positioned nodes. (‘list2.next’)and the next pointer of the last node in the list of even-positioned nodes ‘temp2’ is set to ‘NULL’ to terminate the new linked list.

Now, return the head of the modified linked list of odds elements.
(return list1.next);

Question 30 of 75 - LeetCode Weekly Challenge

Day 66 of 100 Days LeetCode Challenge