Python Algorithm Q18
Q18 Odd Even Linked List
Q
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.
Sample Input
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
Constraints
- n == number of nodes in the linked list
- 0 <= n <= 104
- -106 <= Node.val <= 106
1. My own Solution == Given Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head: #filtering the empty input.
return head
#define odd & even(for readability) and Save start point
head_odd = odd = head
head_even = even = head.next
while even and even.next:
#make it jump two-steps
odd.next, even.next = odd.next.next, even.next.next
odd, even = odd.next, even.next
#combine end of odd and start of even
odd.next = head_even
return head_odd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inp1= [1,2,3,4,5,6,7,8,9]
#function that create linked-list from the list
def makeLinkedList(inp: List) -> ListNode:
node = ListNode()
head = node
for val in inp:
new_node = ListNode(val)
new_node.next = node.next
node.next = new_node
node = node.next
return head
link1 = makeLinkedList(inp1).next
#for test
a = Solution()
head_node = a.oddEvenList(link1)
while head_node:
print(head_node.val)
head_node = head_node.next
No description is needed I think. Refer to the comment above.
Overall Review
The Given Solution is perfectly same with mine!! I made a great progress in handling linked-list, and so proud of myself enduring some confusing and challenging moments. Keep studying hard for the moment when my effort pays off…!!