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, 104].
-106 <= Node.val <= 106
Solutions
Solution 1: Single Pass
We can use two pointers $a$ and $b$ to represent the tail nodes of the odd and even nodes respectively. Initially, pointer $a$ points to the head node $head$ of the list, and pointer $b$ points to the second node $head.next$ of the list. In addition, we use a pointer $c$ to point to the head node $head.next$ of the even nodes, which is the initial position of pointer $b$.
We traverse the list, set pointer $a$ to point to the next node of $b$, i.e., $a.next = b.next$, then move pointer $a$ back by one position, i.e., $a = a.next$; set pointer $b$ to point to the next node of $a$, i.e., $b.next = a.next$, then move pointer $b$ back by one position, i.e., $b = b.next$. Continue to traverse until $b$ reaches the end of the list.
Finally, we set the tail node $a$ of the odd nodes to point to the head node $c$ of the even nodes, i.e., $a.next = c$, then return the head node $head$ of the list.
The time complexity is $O(n)$, where $n$ is the length of the list, and we need to traverse the list once. The space complexity is $O(1)$. We only need to maintain a limited number of pointers.
1 2 3 4 5 6 7 8 9101112131415161718
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defoddEvenList(self,head:Optional[ListNode])->Optional[ListNode]:ifheadisNone:returnNonea=headb=c=head.nextwhilebandb.next:a.next=b.nexta=a.nextb.next=a.nextb=b.nexta.next=creturnhead
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcoddEvenList(head*ListNode)*ListNode{ifhead==nil{returnnil}a:=headb,c:=head.Next,head.Nextforb!=nil&&b.Next!=nil{a.Next=b.Nexta=a.Nextb.Next=a.Nextb=b.Next}a.Next=creturnhead}