328. Odd Even Linked List

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: head = [1,2,3,4,5] Output: [1,3,5,2,4]

Input: head = [2,1,3,5,6,4,7] Output: [2,3,6,7,1,5,4]

Solution Approach

To reorder the given singly linked list such that all nodes with odd indices are grouped together followed by nodes with even indices, we can implement a solution with O(1) extra space complexity and O(n) time complexity.

Algorithm

1. Initialize pointers odd and even to the head of the list and evenHead to the second node (if exists) which will be the head of the even-indexed group.
2. Traverse the list while curr is not None and curr.next is not None.
3. Within the loop: Move odd.next to curr.next to include the current node in the odd-indexed group. Advance odd pointer to the next odd-indexed node. Move curr.next to odd.next to include the next node in the even-indexed group. Advance curr pointer to the next even-indexed node.
4. Once the loop ends, link the end of the odd group with the head of the even group by assigning odd.next to evenHead.
5. Return the head of the modified list.

Implement

    class ListNode:
    def __init__(self, val = 0, next = None):
      self.val = val
      self.next = next
class Solution:
    def oddEvenList(self, head):
      if not head:
        return head
      evenHead = head.next
      odd = head
      curr = head.next
      while curr and curr.next:
        odd.next = curr.next
        odd = odd.next
        curr.next = odd.next
        curr = curr.next
      odd.next = evenHead
      return head

    
       

    
    

Twitter  facebook  Email