# Data Structures & Algorithms in Java – Linked List – Reorder List

## Problem:

Given a singly linked list , reorder it in such a way that the first and last elements are next to each other , the second and second from last are next to each other etc.

For example,

Given the list [1,2,3,4,5]

Reorder it into:

[1,5,2,4,3]

As you see we are merging elements from the first and last together until the list is exhaused.

Try out the solution here:

https://leetcode.com/problems/reorder-list/solution/

## Solution:

Hint:

The solution to this problem involves three major steps:

• Find the middle of the linked list
• Reverse the second half of the linked list
• Merge the first half and the second half

## Explanation:

The steps given in the hint are separate problems themselves and we have already looked into the second and third here:

For finding the middle of the linked list , you maintain two pointers , a slow one and a fast one similar to the ones used to detect a cycle in a linked list.

Both the pointers point to the head element initially and then you increment slow pointer by one node and fast pointer by two nodes. By the time fast pointer reaches the end of the list slow pointer would be pointing to the beginning of the second half.

Here is the code for the same:

```

while(fast!=null && fast.next!=null){

slow = slow.next;

fast = fast.next.next;
}
```

The second step is to reverse the later half.

That can be done by the below code:

```

ListNode newNode = null;

}

return newNode;
}
```

Finally you merge the first half and second half using the below code:

You stop merging when the first half and second don’t collide.

You pick one from each half and keep adding them to a tail node as shown below:

```     ListNode resultHead = new ListNode();

while(first != null && slow != null && first != slow){

resultTail.next = first;

first = first.next;

resultTail = resultTail.next;

resultTail.next = slow;

slow = slow.next;

resultTail = resultTail.next;

}

```

## ALGORITHM:

STEP 1: Initialize two pointers slow and fast

STEP 2: Move slow pointer by one node and fast pointer by two nodes until you reach the end of the list.

STEP 3: The slow pointer now points to the first element of the second half. Using this as head node reverse the second half

STEP 4: Merge the reversed half and the first half (use a pointer to point to the head and use it as the head of the first half)

Here is the full code:

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {

//find middle
while(fast!=null && fast.next!=null){

slow = slow.next;

fast = fast.next.next;
}

//reverse later half
slow =  reverse(slow);

//merge them

while(first != null && slow != null && first != slow){

resultTail.next = first;

first = first.next;

resultTail = resultTail.next;

resultTail.next = slow;

slow = slow.next;

resultTail = resultTail.next;

}

}

ListNode newNode = null;

}

return newNode;
}
}
```

Time complexity of finding the middle element is O(n) , reversing the second half is O(n/2) and merging the two lists is O(n/2).

So total time complexity is O(n)

Space complexity is O(1) since we don’t use any space in proportion to the input. Just a few nodes used as pointers.

That’s it!

Posted

in

by

Tags: