May 11, 2021

Leetcode 143 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.






Input: head = [1,2,3,4]
Output: [1,4,2,3]





Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Soruda bize verilen bir linked listi bir baştan bir sondan olacak şekilde tekrar sıralamamız isteniyor.
Bunun için ilk olarak linked listi ortadan iki parçaya ayırırız. prev = [1,2] second = [3,4]
Daha sonra ikinci parçayı ters çeviririz. second = [4,3]
Şimdi bir birinci listeden bir ikinci listeden eleman alarak yeni listeyi oluşturabiliriz.

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        
        #Linked list ortasını bulalım
        
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        #listeyi ikiye bölelim
        second = slow.next
        prev = slow.next = None
        
        #ikinci parçayı ters çevirelim
        while second:
            tmp = second.next
            second.next = prev
            prev = second
            second = tmp
        
        #iki parçayı aralara koyarak birleştirelim
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2