Reorder List

Question

None

Example 1

None

Solution

▭

all//Reorder List.py

# 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):
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:
            return
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        curr = slow
        prev = None
        while curr:
            _next = curr.next
            curr.next = prev
            prev = curr
            curr = _next
        half1, half2 = head, prev
        while half2.next:
            half1_next = half1.next
            half2_next = half2.next
            half1.next = half2
            half2.next = half1_next
            half1 = half1_next
            half2 = half2_next

▯

all//Reorder List.py

# 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):
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:
            return
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        curr = slow
        prev = None
        while curr:
            _next = curr.next
            curr.next = prev
            prev = curr
            curr = _next
        half1, half2 = head, prev
        while half2.next:
            half1_next = half1.next
            half2_next = half2.next
            half1.next = half2
            half2.next = half1_next
            half1 = half1_next
            half2 = half2_next