[LeetCode] 143 | Reorder List | Python

---

문제 링크: https://leetcode.com/problems/reorder-list/

---

문제

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

---

조건

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

---

내 풀이

입력으로 주어진 리스트(head)를 쭉 읽어 역순에 해당하는 리스트(reHead)를 만든다.

이때, 전체 리스트 길이를 잰다.

입력으로 주어진 리스트(head) 사이사이에 역순에 해당하는 리스트(reHead)를 끼워 넣는다.

언제까지하냐면, 전체 리스트 길이의 절반까지 진행됐을 때까지 진행한다.

---

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if head.next and not head.next.next:
            return
        
        nHead = ListNode(head.val, head.next)
        reHead = ListNode(head.val, None)
        
        a, b = 0, 0
        while nHead.next:
            nHead = nHead.next
            reHead = ListNode(nHead.val, reHead)
            b += 1
            
        while head.next and reHead.next:
            head.next = ListNode(reHead.val, head.next)
            head = head.next.next
            reHead = reHead.next
            a += 1
            b -= 1
            
            if a == b:
                head.next = None
                break
            elif a == b-1:
                head.next.next = None
                break