143. Reorder List

Medium


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.

 

Example 1:

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

Example 2:

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

 

Constraints:

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




 # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotate_last(self, head):
        node = head
        prev = None
        while node:
            temp = node.next 
            node.next = prev
            prev = node
            node = temp

        #self.show(prev)
        return prev

    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        node = head
        slow, fast = node, node

        while fast and fast.next:
            slow = slow.next 
            fast = fast.next.next

        end_head = self.rotate_last(slow.next)
        slow.next = None

        start = head

        while start and end_head:
            start_next = start.next 
            end_next = end_head.next 
            start.next = end_head
            end_head.next = start_next

            start = start_next
            end_head = end_next

        return head

Random Note


  1. Effectively Using Django REST Framework Serializers
  2. How To Use DRF Serializers Effectively in Django
  3. My personal django rest framework serializer notes
  4. How to use DRF serializers effectively during write operations