on
[LeetCode]328. Odd Even Linked List — 홀짝 연결 리스트 8-18. —
[LeetCode]328. Odd Even Linked List — 홀짝 연결 리스트 8-18. —
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 <= 104
-106 <= Node.val <= 106
# ------------------------------------------------------
# Definition for singly-linked list.
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next # Definition to make List into ListNode # No need for LeetCode, only for local editors. def makeNode(self, lst): res = ptr = ListNode() for item in lst: ptr.next = ListNode(item) ptr = ptr.next return res.next # Definition to make ListNode into List # No need for LeetCode, only for local editors. def nodesToList(self, node): rLst = [] while node: if node: rLst.append(node.val) node = node.next return rLst
# Solution 1.
Loop Sturcture
from typing import Optional class Solution: def oddEvenList(self, head:Optional[ListNode]) -> Optional[ListNode]: # Exception handling if head is None: return None odd = head even = head.next even_head = head.next # node processing(handling) while looping while even and even.next: odd.next, even.next = odd.next.next, even.next.next odd, even = odd.next, even.next # Link the last odd node to the head of even node ( 홀수 노드의 마지막을 짝수 헤드로 ) odd.next = even_head return head
# Execute
l1 = [1,2,3,4,5] l2 = [2,1,3,5,6,4,7] lstNd = ListNode() h1 = lstNd.makeNode(l1) h2 = lstNd.makeNode(l2) res1 = Solution().oddEvenList(h1) res2 = Solution().oddEvenList(h2) print(lstNd.nodesToList(res1)) print(lstNd.nodesToList(res2))
p.233
from http://raejin.tistory.com/76 by ccl(A) rewrite - 2021-09-01 15:00:31