Reorder Linked List in DSA Python - Build from Scratch

Reorder Linked List

📖 Scenario: You have a singly linked list representing a queue of people waiting in line. Sometimes, the queue needs to be reordered so that the first person is followed by the last person, then the second person, then the second last person, and so on.For example, if the queue is 1 -> 2 -> 3 -> 4 -> 5, after reordering it becomes 1 -> 5 -> 2 -> 4 -> 3.

🎯 Goal: You will build a program that reorders a singly linked list in this special pattern: first node, last node, second node, second last node, and so on.

📋 What You'll Learn

Create a singly linked list with nodes containing integer values

Find the middle of the linked list

Reverse the second half of the linked list

Merge the two halves by alternating nodes

Print the reordered linked list

💡 Why This Matters

🌍 Real World

Reordering linked lists is useful in scenarios like rearranging queues, scheduling tasks, or organizing data streams where alternating order is needed.

💼 Career

Understanding linked list manipulation is important for software engineering roles that involve data structure optimization, memory management, and algorithm design.

1

Create the linked list

Create a class called Node with attributes val and next. Then create a linked list with nodes having values 1, 2, 3, 4, and 5 linked in order. Store the head node in a variable called head.

DSA Python

# Define Node class and create linked list with values 1 to 5
# Your code here

Hint

Define a Node class with val and next. Then link nodes with values 1 to 5.

2

Find the middle of the linked list

Create two pointers called slow and fast starting at head. Move slow by one node and fast by two nodes in a loop until fast reaches the end. This will find the middle node. Store the middle node in slow.

DSA Python

slow = head
fast = head
# Move slow by one and fast by two until fast reaches the end
# Your code here

Hint

Use two pointers: slow moves one step, fast moves two steps until fast reaches the end.

3

Reverse the second half of the linked list

Starting from the node after slow, reverse the linked list nodes until the end. Use variables prev set to None and curr set to slow.next. Iterate through the nodes, reversing the links. After reversing, set slow.next to None to split the list.

DSA Python

prev = None
curr = slow.next
# Reverse the second half of the list
# Your code here

Hint

Reverse the nodes starting from slow.next by changing their next pointers.

4

Merge the two halves and print the reordered list

Merge the first half starting at head and the reversed second half starting at prev by alternating nodes. Use pointers first and second. After merging, print the reordered list values separated by ' -> ' and ending with ' -> null'.

DSA Python

first = head
second = prev
# Merge the two halves by alternating nodes
# Print the reordered list
# Your code here

Hint

Alternate nodes from the first half and reversed second half. Then print the list values with ' -> ' between them and end with ' -> null'.