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]
- 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 reorderList(self, head: ListNode) -> None: """ Do not return anything, modify head in-place instead. """ if head == None: return  slow = head fast = head.next while fast and fast.next: fast = fast.next.next slow = slow.next second_list = slow.next slow.next = None prev = None curr = second_list while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt second_list = prev first_list = head while second_list: temp1 = first_list.next temp2 = second_list.next second_list.next = None first_list.next = second_list second_list.next = temp1 first_list = first_list.next.next second_list = temp2 return head