Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
My idea is to construct a list containing all of the even nodes of the list, while removing these nodes from the original list
After this seconday list is made, it is tacked to the end of the original list which had its even number removed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | # 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: ListNode) -> ListNode:
#head is the odd list
#build the even list and tack it to the end
if head is None:
return head
if head.next is None:
return head
even = True
l_odd=head
l_even = ListNode()
even_head = l_even
chaser = head
head = head.next
while head:
if even:
chaser.next = head.next
even_head.next = head
even_head = even_head.next
chaser2= chaser
chaser = head
head = head.next
even = not even
even_head.next = None
if not even:
chaser2.next = l_even.next
else:
chaser.next = l_even.next
return l_odd
|
Like this post? Share on:
Twitter
❄ Facebook
❄ Email