#328

Odd Even Linked List

specialist · 675 · lc medium +30 · verified · 62.3% accepted · 11,423 likes · top 63%

Description

Given the head of a singly linked list, rearrange the nodes so all odd-indexed nodes appear before all even-indexed nodes, preserving the original relative order within each group. Index numbering starts at 1 (first node is odd, second is even, etc.).

Achieve this in O(1) extra space and O(n) time.

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]

Code

# 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: Optional[ListNode]) -> Optional[ListNode]:

# 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: Optional[ListNode]) -> Optional[ListNode]: