Reorder Linked List

Given Linked List

Need to reorder the linked list like bellow

Intuition

If you notice properly, the solution expects you to take one node from the Left/Start of the list and another node from Right/End of the list and repeat until all of the nodes are re-orderd.

So the Left pointer must move forward and the Right needs to move backward. But moving backward in a Singly Linked List is impossible unless the Linked List got reversed.
To solve this problem at first we need to

1. Split the Linked List into Two Halves.
   1. Find the node Before Middle Node
   2. Split the Linked List into Two Halves
2. Reverse the Second Half of the Linked List
   the 2nd Half of the list needs to be Reversed so that the Right pointer can move forward on the reversed linked list which depicts moving backward to a linked list.

As the Right pointer moves, each node it's pointing to the 2nd Half will be added next to the Left pointer position at the 1st Half of the linked list.

Now you may ask why will we take nodes from 2nd half and add to the 1st half accordingly?
Because we are not going to use extra memory by constructing a new linked list rather modify the node positions in the given linked list like shifting node positions.

No worries, we will get it done step by step

Keeping in mind that we need to reverse the 2nd Half. To do so, we need to divide the Linked List into two separate lists. To divide the lists into two halves, we need to place a pointer before the middle node of the linked list first. So our First goal is to place a pointer before the middle node.

Step 1: Find the Node before middle

Let's visualize out thinking first

Let's implement it in a helper function

def getNodeBeforeMid(self, head: Optional[ListNode]) -> Optional[ListNode]:
	slow = head
	fast = head.next  # because we need to find the node before middle
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	return slow

Step 2: Divide the Linked List into Two Halves

Now we have the node before the middle node of the Linked List. Let's separate both of these halves. Call the helper function getNodeBeforeMid from the main function

def reorderList(self, head: Optional[ListNode]) -> None:
	if not head:
		return
	before_mid = self.getNodeBeforeMid(head)
	sec_head = before_mid.next  # saving the head of 2nd half
	before_mid.next = None  # separating the list into two halves

Let's visualize the output

Now we have 2 separate Linked Lists and breaking the link between them is Important.
Our next goal is to Reverse the 2nd Half.

Step 3: Reverse the 2nd Half

Let's write another helper function, but before that let's visualize what are we going to do.

We have reversed the .next pointer of curr node to point it's previous node. Repeat these steps until the curr pointer reaches to NULL (i.e. End of the Linked List)

The curr has reached to the end that means the 2nd Half is completely reversed. The prev node is the new Reversed HEAD of the 2nd Half. Let's implement this part

def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:
	prev = None
	curr = head
	while head:
		curr_next = curr.next
		# reversing the link
		curr.next = prev
		prev = curr
		curr = curr_next
	return prev

Step 4: Reorder the List

Since we got the 2nd Half Reversed, Let's Attach nodes from this 2nd Half one by one with the First Half. To do so, we will use two pointers p1 and p2 where p1 is pointing at the HEAD of the First Half and p2 is pointing at the Reversed Head of the Second Half
Let's Iterate over

We gonna Iterate over Second Half and repeat the same process until p2 reaches the end of Second Half (i.e. p2 == None)

This is it, The Linked List is re-ordered. Let's accumulate the piece of code snippets.

Complete Code Snippet

# 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: Optional[ListNode]) -> None:
		if not head:
			return

		before_mid = self.getNodeBeforeMid(head)
		sec_head = before_mid.next

		# break the link to saperate into two halves
		before_mid.next = None
		
		# reverse the second half
		rev_head = self.reverse(sec_head)
		
		# Re-order
		p1 = head
		p2 = rev_head
		while p2:
		# saving next pointer for further use

			p1_next = p1.next
			p2_next = p2.next
			
			# re-connect nodes
			p1.next = p2
			p2.next = p1_next
			
			# move pointers forward
			p1 = p1_next
			p2 = p2_next


	def getNodeBeforeMid(self, head: Optional[ListNode]) -> Optional[ListNode]:
		slow = head
		fast = head.next
		while fast and fast.next:
			slow = slow.next  # moving 1 step
			fast = fast.next.next  # moving 2 steps
			return slow

	def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:
		prev = None
		curr = head
		while curr:
			curr_next = curr.next  # saving next node for further use
			curr.next = prev  # linking with the prev node
			prev = curr  # move prev forward
			curr = curr_next  # move curr forward
		
		return prev

That's pretty much it. Thanks for stopping by!

Connect with me on