tags: LeetCode,Python3,Medium

143. Reorder List

題目連結： Reorder List

解題方向

• 這題跟 234. Palindrome Linked List很像，只是多了merge而已
• 用快慢指標找中間點
• 把後半段reverse
• merge前半跟reverse過的後半

完整程式碼

# 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:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return
        slow = head
        fast = head
        prev = head
        while fast and fast.next:
            prev = slow
            fast = fast.next.next
            slow = slow.next
        prev.next = None # 把前半的尾端指向None，而不是slow
        list1 = head
        list2 = self.reverse(slow) # 反轉後半的list
        self.merge(list1, list2)

    def reverse(self, head):
        if not head:
            return None
        prev = None
        curr = head
        while curr:
            nextNode = curr.next
            curr.next = prev
            prev = curr
            curr = nextNode
        return prev

    def merge(self, list1, list2):
        while list2:
            nextNode = list1.next
            list1.next = list2
            list1 = list2
            list2 = nextNode