328. Odd Even Linked List - python3

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 Answer 1: Accepted (Runtime: 44 ms - 56.34% / Memory Usage: 16.4 MB - 11.34%)

# 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:
        if head is None:
            return head
        
        count = 0
        head2 = ListNode(0, None)
        
        head3 = head
        head4 = head2
        
        while head.next:
            if count%2 == 0:
                head2.next = head.next
                head2 = head2.next
                head.next = head2.next
                head2.next = None
            else:
                head = head.next
            count += 1
        
        head4 = head4.next
        head.next = head4
        
        return head3

1. head 가 None 일 때 예외처리

2. 짝수번째 노드를 저장할 head2 선언

3. head3 는 head 의, head4 는 head2 의 맨 앞자리 위치를 잡아주는 역할

4. head.next 가 존재할 때만 반복문을 돌면서
   짝수번째 노드면 head2 에 저장해주고 head 에서 짝수 노드를 건너뛰도록

5. head4 의 맨 앞은 0 이므로 head4 = head4.next

6. head 의 맨 뒤에 짝수번째 노드가 저장된 head4 를 붙여줌

7. head 의 맨 앞자리인 head3 반환

뭔가 런타임이나 메모리는 내멋대로 한듯..^^

O(N) time, O(1) space

Solution 1: Accepted (Runtime: 44 ms - 56.34% / Memory Usage: 16.4 MB - 11.34%)

# 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:
        if head is None or head.next is None:
            return head
        oddHead = head
        evenStart = head.next
        evenHead = head.next
        
        while evenHead:
            oddHead.next = evenHead.next
            if oddHead.next:
                oddHead = oddHead.next
            evenHead.next = oddHead.next
            evenHead = evenHead.next
        oddHead.next = evenStart
        
        return head

oddHead, evenHead, evenStart 를 이용해서 하기