[LeetCode] 328. Odd Even Linked List

328. Odd Even Linked List

Medium

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:

• The number of nodes in the linked list is in the range [0, 104].
• -106 <= Node.val <= 106

---

문제 풀이

• 링크드 리스트가 주어진다.
• 짝수 번째의 노드들을 모두 연결하고 홀수 번째의 노드들을 모두 연결한다.
• 맨앞에 홀수 번째로 구성된 링크드리스트가 있어야하며 그 뒤에는 짝수 번째의 노드들이 연결되어야한다.
• 공간 복잡도는 O(1) 상수 크기 만큼만 사용하고 시간 복잡도는 O(n)로 풀라고 나와있다. 
• 홀수 번째 노드들을 각각 연결해나가면서, 짝수 번째 노드들도 연결한다.
• 마지막에 짝수 번째의 헤드를 모든 과정이 끝나고 홀수 번째 노드 끝에 연결한다. 

소스 코드

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if head == None: return head
        odd = head
        even = head.next
        evenhead = even
        while even != None and even.next != None:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = evenhead
        return head