LeetCode 328 Odd Even Linked List

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 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:

n ==number of nodes in the linked list 0 <= n <= 10<sup>4</sup>
* -10<sup>6</sup> <= Node.val <= 10<sup>6</sup>

题目大意：

重排LL， 先偶位再奇位

解题思路：

N/A

解题步骤：

N/A

注意事项：

1. LL四点注意事项： 删除节点.next = None
2. 空输入特别处理

Python代码：

def oddEvenList(self, head: ListNode) -> ListNode:
	if not head: # remember
		return None
	odd_head = ListNode(0)
	it, it_odd = head, odd_head
	while it.next:
		it_odd.next = it.next
		it.next = it.next.next
		if it.next:
			it = it.next
		it_odd = it_odd.next
		it_odd.next = None # remember
	it.next = odd_head.next
	return head

算法分析：

时间复杂度为O(n)，空间复杂度O(1)