## Facebook Interview Question

**Country:**United States

**Interview Type:**Phone Interview

I like this stack approach, the stack is only keeping references to the nodes; so one could argue that it's not strictly O(n) on memory...

```
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function(head) {
if (!head || !head.next) return head
// 1. find the middle node O(n)
let slow = head
let fast = head.next
while (fast && fast.next) {
fast = fast.next.next
slow = slow.next
}
// 2. reverse from middle
let newHead = null
let curr = slow.next
slow.next = null
while (curr) {
const next = curr.next
curr.next = newHead
newHead = curr
curr = next
}
// 3. merge mid and head
let currHead = head
let currMid = newHead
while (currHead && currMid) {
const headNext = currHead.next
const midNext = currMid.next
currHead.next = currMid
currMid.next = headNext
currHead = headNext
currMid = midNext
}
return head
};
```

```
public static void ReorderLinkedList(LinkedList<char> list)
{
if (!list.Any())
{
throw new ArgumentNullException(nameof(list));
}
var length = list.Count - 1;
for (int i = 0; i <= length / 2; i++)
{
if (i % 2 != 0)
{
continue;
}
var first = list.ElementAt(i);
var nodeFirst = list.Find(first);
var last = list.ElementAt(length);
list.AddAfter(nodeFirst, last);
list.RemoveLast();
}
foreach (var element in list)
{
Console.Write(string.Concat(element, " "));
}
}
```

```
public void reorderList(ListNode head) {
Stack<ListNode> stack = new Stack<ListNode>();
int size = 0;
ListNode current = head;
while(current!=null){
stack.push(current);
current = current.next;
size++;
}
int counter = 0;
current = head;
while(current!=null&&counter<size/2){
ListNode next = current.next;
ListNode popped = stack.pop();
popped.next = next;
current.next = popped;
current = popped.next;
counter++;
}
current.next = null;
}
```

class Solution {

ListNode left=null;

public void reorderList(ListNode head) {

if(head==null) return;

left=head;

myList(head);

}

public void myList(ListNode root)

{

if(root==null) return;

myList(root.next);

if(left.next==null) return;

ListNode t=left.next;

if(left.next==root)

{

root.next=null; return;

}

if(t.next== root) t.next=null;

left.next=root;

root.next=t;

left=t;

}

}

class Solution {

ListNode left=null;

public void reorderList(ListNode head) {

if(head==null) return;

left=head;

myList(head);

}

public void myList(ListNode root)

{

if(root==null) return;

myList(root.next);

if(left.next==null) return;

ListNode t=left.next;

if(left.next==root)

{

root.next=null; return;

}

if(t.next== root) t.next=null;

left.next=root;

root.next=t;

left=t;

}

}

class Solution {

ListNode left=null;

public void reorderList(ListNode head) {

if(head==null) return;

left=head;

myList(head);

}

public void myList(ListNode root)

{

if(root==null) return;

myList(root.next);

if(left.next==null) return;

ListNode t=left.next;

if(left.next==root)

{

root.next=null; return;

}

if(t.next== root) t.next=null;

left.next=root;

root.next=t;

left=t;

}

}

class Solution {

ListNode left=null;

public void reorderList(ListNode head) {

if(head==null) return;

left=head;

myList(head);

}

public void myList(ListNode root)

{

if(root==null) return;

myList(root.next);

if(left.next==null) return;

ListNode t=left.next;

if(left.next==root)

{

root.next=null; return;

}

if(t.next== root) {

t.next=null;

}

left.next=root;

root.next=t;

left=t;

}

}

Inplace through recusion

```
class Solution {
public void reorderList(ListNode head) {
reorder(head, head);
}
private ListNode reorder(ListNode slow, ListNode fast) {
if (fast == null) {
return slow;
}
if (fast.next == null) {
ListNode toRet = slow.next;
slow.next = null;
return toRet;
}
ListNode reNext = reorder(slow.next, fast.next.next);
ListNode toRet = reNext.next;
reNext.next = slow.next;
if (reNext.next == reNext) {
reNext.next = null;
}
slow.next = reNext;
return toRet;
}
}Solution {
public void reorderList(ListNode head) {
reorder(head, head);
}
private ListNode reorder(ListNode slow, ListNode fast) {
if (fast == null) {
return slow;
}
if (fast.next == null) {
ListNode toRet = slow.next;
slow.next = null;
return toRet;
}
ListNode reNext = reorder(slow.next, fast.next.next);
ListNode toRet = reNext.next;
reNext.next = slow.next;
if (reNext.next == reNext) {
reNext.next = null;
}
slow.next = reNext;
return toRet;
}
}
```

In place through recursion :

1. Handle even and odd length lists (check comments)

2. reach middle point through slow and fast pointers, which should both be initialized from head. (reorder(head, head)).

3. Basic idea is that once middle is reached than return the next element which your parent should point towards now.

For e.,g. 1->2->3->4->5->6->7->

ans : 1->7->2->6->3->5->4->

when 4 is reached (which you would know if the fast pointer reaches 7)

it should return 5 so that 3 makes 5 as its next element. but before that, 5 should point to what 3 was pointing towards. and even before that, cache 5's next to be returned for this call of recursion.

```
ListNode reNext = reorder(slow.next, fast.next.next);
ListNode toRet = reNext.next;
reNext.next = slow.next;
```

```
slow.next = reNext;
return toRet;
```

now once the stack unfurls at 4, 4 would return its next which is 5, which would return 6, which would return 7 and so on :

some special cases needs to be handled for even and odd lengths, if they are not clear enough do let me know.

Over all code :

```
class Solution {
public void reorderList(ListNode head) {
reorder(head, head);
}
private ListNode reorder(ListNode slow, ListNode fast) {
if (fast == null) {
return slow;
}
if (fast.next == null) {
ListNode toRet = slow.next;
slow.next = null;
return toRet;
}
ListNode reNext = reorder(slow.next, fast.next.next);
ListNode toRet = reNext.next;
reNext.next = slow.next;
if (reNext.next == reNext) {
reNext.next = null;
}
slow.next = reNext;
return toRet;
}
}
```

In place through recursion :

1. Handle even and odd length lists (check comments)

2. reach middle point through slow and fast pointers, which should both be initialized from head. (reorder(head, head)).

3. Basic idea is that once middle is reached than return the next element which your parent should point towards now.

For e.,g. 1->2->3->4->5->6->7->

ans : 1->7->2->6->3->5->4->

when 4 is reached (which you would know if the fast pointer reaches 7)

it should return 5 so that 3 makes 5 as its next element. but before that, 5 should point to what 3 was pointing towards. and even before that, cache 5's next to be returned for this call of recursion.

```
ListNode reNext = reorder(slow.next, fast.next.next);
ListNode toRet = reNext.next;
reNext.next = slow.next;
```

```
slow.next = reNext;
return toRet;
```

now once the stack unfurls at 4, 4 would return its next which is 5, which would return 6, which would return 7 and so on :

some special cases needs to be handled for even and odd lengths, if they are not clear enough do let me know.

Over all code :

```
class Solution {
public void reorderList(ListNode head) {
reorder(head, head);
}
private ListNode reorder(ListNode slow, ListNode fast) {
if (fast == null) {
return slow;
}
if (fast.next == null) {
ListNode toRet = slow.next;
slow.next = null;
return toRet;
}
ListNode reNext = reorder(slow.next, fast.next.next);
ListNode toRet = reNext.next;
reNext.next = slow.next;
if (reNext.next == reNext) {
reNext.next = null;
}
slow.next = reNext;
return toRet;
}
}
```

In place through recursion :

1. Handle even and odd length lists (check comments)

2. reach middle point through slow and fast pointers, which should both be initialized from head. (reorder(head, head)).

3. Basic idea is that once middle is reached than return the next element which your parent should point towards now.

For e.,g. 1->2->3->4->5->6->7->

ans : 1->7->2->6->3->5->4->

when 4 is reached (which you would know if the fast pointer reaches 7)

it should return 5 so that 3 makes 5 as its next element. but before that, 5 should point to what 3 was pointing towards. and even before that, cache 5's next to be returned for this call of recursion.

```
ListNode reNext = reorder(slow.next, fast.next.next);
ListNode toRet = reNext.next;
reNext.next = slow.next;
```

```
slow.next = reNext;
return toRet;
```

now once the stack unfurls at 4, 4 would return its next which is 5, which would return 6, which would return 7 and so on :

some special cases needs to be handled for even and odd lengths, if they are not clear enough do let me know.

Over all code :

```
class Solution {
public void reorderList(ListNode head) {
reorder(head, head);
}
private ListNode reorder(ListNode slow, ListNode fast) {
if (fast == null) {
return slow;
}
if (fast.next == null) {
ListNode toRet = slow.next;
slow.next = null;
return toRet;
}
ListNode reNext = reorder(slow.next, fast.next.next);
ListNode toRet = reNext.next;
reNext.next = slow.next;
if (reNext.next == reNext) {
reNext.next = null;
}
slow.next = reNext;
return toRet;
}
}
```

Not sure if this can be done in-memory, I have however used stack iteratively with Deque implementation. Here is the code :

- getPDat February 03, 2019