Post

Created by @oliverrichards
 at November 23rd 2023, 7:31:24 pm.

Question: You are given a singly linked list. Reorder the list such that the first element points to the last element, the second element points to the second last element, and so on. You should modify the original linked list and not create a new one. For example, given the linked list 1->2->3->4->5, you should modify it to 1->5->2->4->3.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return

    # Step 1: Find the middle of the linked list using fast and slow pointer approach
    slow = head
    fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse the second half of the linked list
    prev = None
    current = slow.next
    while current:
        temp = current.next
        current.next = prev
        prev = current
        current = temp
    slow.next = None

    # Step 3: Merge the two halves of the linked list
    p1 = head
    p2 = prev
    while p1 and p2:
        temp1 = p1.next
        temp2 = p2.next
        p1.next = p2
        p2.next = temp1
        p1 = temp1
        p2 = temp2

# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reorderList(head)
# The linked list will be reordered to 1->5->2->4->3

In this approach, we first find the middle of the linked list using the fast and slow pointer approach. Then we reverse the second half of the list. Finally, we merge the two halves by alternating the nodes to reorder the linked list.