## 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;
}
}
```

Here is recursive python implementation

```
class Node:
def __init__(self,val):
self.val = val
self.next = None
def __repr__(self):
head = self
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string
class Llist:
def __init__(self):
self.head = None
self.tail = None
def insert(self, val):
node = Node(val)
if not self.head:
self.tail = self.head = node
else:
self.tail.next = node
self.tail = node
return True
def __repr__(self):
head = self.head
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string
def modify_list(head):
global global_head, flag, return_head
if not head:
return head
print("called", head.val)
temp = modify_list(head.next)
if not flag:
return return_head
if not temp:
return_head = global_head
if head!=global_head:
temp_global = global_head
if temp:
temp.next = global_head
head.next = None
global_head = global_head.next
temp_global.next = head
else:
temp.next = head
head.next = None
#print(global_head)
flag=False
#print(head.val, global_head, return_head)
if head==global_head:
flag=False
return head
llist1 = Llist()
llist1.insert('A')
llist1.insert('B')
llist1.insert('C')
llist1.insert('D')
llist1.insert('E')
llist1.insert('F')
print(llist1)
global_head= llist1.head
flag = True
return_head = None
print(modify_list(llist1.head))
```

class Node:

def __init__(self,val):

self.val = val

self.next = None

def __repr__(self):

head = self

string = ""

while(head):

string += str(head.val) + ','

head = head.next

return string

class Llist:

def __init__(self):

self.head = None

self.tail = None

def insert(self, val):

node = Node(val)

if not self.head:

self.tail = self.head = node

else:

self.tail.next = node

self.tail = node

return True

def __repr__(self):

head = self.head

string = ""

while(head):

string += str(head.val) + ','

head = head.next

return string

def modify_list(head):

global global_head, flag, return_head

if not head:

return head

print("called", head.val)

temp = modify_list(head.next)

if not flag:

return return_head

if not temp:

return_head = global_head

if head!=global_head:

temp_global = global_head

if temp:

temp.next = global_head

head.next = None

global_head = global_head.next

temp_global.next = head

else:

temp.next = head

head.next = None

#print(global_head)

flag=False

#print(head.val, global_head, return_head)

if head==global_head:

flag=False

return head

llist1 = Llist()

llist1.insert('A')

llist1.insert('B')

llist1.insert('C')

llist1.insert('D')

llist1.insert('E')

llist1.insert('F')

print(llist1)

global_head= llist1.head

flag = True

return_head = None

print(modify_list(llist1.head))

```
static Node screw(Node in) {
Node reversed = reverse(in);
Node screwedNode = new Node();
Node screwedCurr = screwedNode;
Node currIn = in;
Node currRev = reversed;
int length = length(in);
for (int i=0; i<length; i++) {
if (i%2==0) {
screwedCurr.value = currIn.value;
currIn = currIn.next;
} else {
screwedCurr.value = currRev.value;
currRev = currRev.next;
}
if (i<length-1) {
screwedCurr.next = new Node();
screwedCurr = screwedCurr.next;
}
}
return screwedNode;
}
static int length(Node in) {
int counter = 1;
while((in = in.next) != null) counter++;
return counter;
}
static Node reverse(Node in) {
Node reverse = clone(in);
Node curr = reverse;
Node prev = curr;
Node next;
while (true) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
if (curr == null) break;
}
reverse.next = null;
return prev;
}
private static Node clone(Node in) {
Node clone = new Node();
Node cloneCurr = clone;
cloneCurr.value = in.value;
while((in = in.next) != null) {
cloneCurr.next = new Node();
cloneCurr = cloneCurr.next;
cloneCurr.value = in.value;
}
return clone;
}
```

```
import java.util.*;
public class ManageList{
public static void main(String[] args){
Node head = new Node('A');
Node cur = head;
cur.next = new Node('B');
cur = cur.next;
cur.next = new Node('C');
cur = cur.next;
cur.next = new Node('D');
cur = cur.next;
cur.next = new Node('E');
Node mid = getMid(head);
Node newHead = reverse(mid);
Node total = combine(head, newHead);
while(total != null){
System.out.println(total.val);
total = total.next;
}
}
public static Node combine(Node a, Node b){
Node dummy = new Node('*');
Node curr = dummy;
while(a != null || b != null){
if(a != null && b != null){
curr.next = a;
a = a.next;
curr = curr.next;
curr.next = b;
b = b.next;
curr = curr.next;
}else if(a != null){
curr.next = a;
a = a.next;
curr = curr.next;
}else if(b != null){
curr.next = b;
b = b.next;
curr = curr.next;
}
}
return dummy.next;
}
public static Node getMid(Node node){
Node fast = node;
Node slow = node;
Node prev = null;
while(fast != null && fast.next != null){
fast = fast.next.next;
prev = slow;
slow = slow.next;
}
prev.next = null;
return slow;
}
public static Node reverse(Node node){
Node prev = null;
Node curr = node;
Node next = node.next;
while(next != null){
curr.next = prev;
Node temp = next.next;
next.next = curr;
prev = curr;
curr = next;
next = temp;
}
return curr;
}
}
class Node{
Node next;
char val;
Node(char val){
this.val = val;
next = null;
}
}
```

```
//LinkedList :
// Input: A > B > C > D > E
// Output: A > E > B > D > C
// A, [B,C,D,E] => [E,C,D,B]
// E, [C,D,B] => [B,D,C]
// B, [D,C] => [D,C]
class Node {
constructor(data) {
this.data = data
this.next = null
this.previous = null
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
add(data) {
let node = new Node(data)
if (!this.head) {
this.head = node
}
if (this.tail) {
this.tail.next = node
node.previous = this.tail
}
this.tail = node
this.length++
}
get(index) {
if (!this.head)
return null
if (index <= 0)
return this.head
if (index >= this.length-1)
return this.tail
let current = this.head
for (let i = 1; i <= index; i++) {
if (!current.next)
return null
current = current.next
}
return current
}
remove(index) {
let len = this.length
if(index == 0) {
let current = this.head
current.next.previous = null
this.head = current.next
this.length--
if(this.tail == current)
this.tail = current.next
current.next = null
return current
}
if (index >= len-1) {
let current = this.tail
current.previous.next = null
this.tail = current.previous
this.length--
if(this.head == current)
this.head = current.previous
current.previous = null
return current
}
let current = this.get(index)
current.previous.next = current.next
current.next.previous = current.previous
this.length--
current.next = null
current.previous = null
return current
}
switch(from, to) {
if (from == to)
return
let fromNode = this.get(from)
let toNode = this.get(to)
let data = fromNode.data
fromNode.data = toNode.data
toNode.data = data
}
print() {
let data = []
for(let current = this.head; current != null; current = current.next) {
data.push(current.data)
}
console.log(data)
}
}
const list = new LinkedList()
list.add('A')
list.add('B')
list.add('C')
list.add('D')
list.add('E')
for (let i = 1; i < list.length-2; i++) {
list.switch(i, list.length)
list.print()
}
```

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