Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
class Link{
constructor(data){
this.data = data;
this.child = null;
}
addChild(child){
if(!(child instanceof Link)){
throw 'Error';
}
this.child = child;
}
}
let link = new Link(1);
let head = link;
for(var i = 2 ; i < 10 ; i++){
link.addChild(new Link(i));
link = link.child;
}
function printAll(link){
while(link ){
console.log(link.data);
link = link.child;
}
}
function findMiddle(link){
let slow = link;
let fast = link;
while(fast && fast.child){
fast = fast.child;
if(fast){
fast = fast.child;
}
link = link.child;
}
return link;
}
function reverse(link, prev){
if(!link.child){
link.child = prev;
return link; //this will be the new head
}
let child = link.child;
link.child = prev;
return reverse(child,link);
}
function combineLinks(l1,l2){
let current = l1;
let head = l1;
let isL1 = true;
while(l1 && l2){
if(isL1){
l1 = l1.child;
current.child = l2;
}else{
l2 = l2.child;
current.child = l1;
}
current = current.child;
isL1 = !isL1;
}
return head;
}
function rearrange(link){
let middle = findMiddle(link);
let reverseHalf = middle.child;
middle.child = null;
reverseHalf = reverse(reverseHalf, null);
return combineLinks(link,reverseHalf);
}
printAll(rearrange(head));
Answer using JavaScript
class Link{
constructor(data){
this.data = data;
this.child = null;
}
addChild(child){
if(!(child instanceof Link)){
throw 'Error';
}
this.child = child;
}
}
let link = new Link(1);
let head = link;
for(var i = 2 ; i < 10 ; i++){
link.addChild(new Link(i));
link = link.child;
}
function printAll(link){
while(link ){
console.log(link.data);
link = link.child;
}
}
function findMiddle(link){
let slow = link;
let fast = link;
while(fast && fast.child){
fast = fast.child;
if(fast){
fast = fast.child;
}
link = link.child;
}
return link;
}
function reverse(link, prev){
if(!link.child){
link.child = prev;
return link; //this will be the new head
}
let child = link.child;
link.child = prev;
return reverse(child,link);
}
function combineLinks(l1,l2){
let current = l1;
let head = l1;
let isL1 = true;
while(l1 && l2){
if(isL1){
l1 = l1.child;
current.child = l2;
}else{
l2 = l2.child;
current.child = l1;
}
current = current.child;
isL1 = !isL1;
}
return head;
}
function rearrange(link){
let middle = findMiddle(link);
let reverseHalf = middle.child;
middle.child = null;
reverseHalf = reverse(reverseHalf, null);
return combineLinks(link,reverseHalf);
}
printAll(rearrange(head));
/*
Solution in O(N) runtime and O(1) space
1) step through the list to determine the size
2) invert 2nd half of the list
3) shuffle together
*/
#include <iostream>
struct Item
{
Item* next_;
int value_;
Item(int value, Item* next) : next_(next), value_(value) { }
};
size_t getSize(Item* item);
Item* getKthItem(Item* item, size_t k);
Item* invertList(Item* item);
void printList(Item* item);
void shuffleList(Item* item)
{
size_t n = getSize(item);
if(n <= 2) return;
Item* lastFirstHalf = getKthItem(item, n / 2 - 1);
Item* lastSeconHalf = lastFirstHalf->next_;
Item* secondHalf = invertList(lastSeconHalf);
Item* firstHalf = item;
lastFirstHalf->next_ = nullptr;
while(firstHalf != nullptr) {
Item* current = firstHalf;
firstHalf = firstHalf->next_;
current->next_ = secondHalf;
secondHalf = secondHalf->next_;
current->next_->next_ = firstHalf;
}
}
int main()
{
Item *list = new Item(1,
new Item(2,
new Item(3,
new Item(4,
new Item(5,
new Item(6, nullptr))))));
shuffleList(list);
printList(list);
}
Item* invertList(Item* item)
{
Item* prev = nullptr;
Item* next = nullptr;
while(item != nullptr) {
next = item->next_;
item->next_ = prev;
prev = item;
item = next;
}
return prev;
}
Item* getKthItem(Item* item, size_t k) {
while(k > 0 && item != nullptr) {
item = item->next_;
k--;
}
return item;
}
size_t getSize(Item* item) {
size_t size = 0;
while(item != nullptr) {
item = item->next_;
size++;
}
return size;
}
void printList(Item* item)
{
while(item != nullptr) {
std::cout << item->value_ << " ";
item = item->next_;
}
}
public class Jumble {
static class Node {
Node(int val) {
this.val =val;
}
int val;
Node next;
}
static void connect(Node node) {
//single node return;
if(node.next == null) {
return;
}
//double node return;
if(node.next.next == null) {
return;
}
Node head = new Node(-1);
head.next = node;
Node prev = null;
while(node.next != null) {
prev = node;
node = node.next;
}
Node second = head.next.next;
node.next = second;
head.next.next = node;
prev.next = null;
}
static Node jumble(Node node) {
Node head = new Node(-1);
head.next = node;
do {
connect(node);
if(node.next != null) {
node = node.next.next;
}
} while(node != null && node.next != null);
return head.next;
}
public static void main(String... args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
Node s = n1;
System.out.print("Before::");
while(n1 != null) {
System.out.print(n1.val + "->");
n1 = n1.next;
}
jumble(s);
System.out.println();
System.out.print("After:: ");
while(s != null) {
System.out.print(s.val+ "->");
s = s.next;
}
}
}
def spiral(self):
partial = self.head
finished = False
while not finished:
finished = True
cur = partial
while cur and cur.node and cur.node.node:
finished = False
cur = cur.node
if not finished:
temp = cur.node
cur.node = None
cur = partial
partial = cur.node
cur.node = temp
cur.node.node = partial
There is a simple way of doing this. Get the first node and concatenate to it the rest of the list but with the last node first. Then skip one node and repeat.
class Node:
def __init__(self,data,next=None):
self.data = data
self.next = next
def last_first(node):
if node == None: return None
if node.next == None: return node
first = node
while node.next.next:
node = node.next
last = node.next
node.next = None
last.next = first
return last
def process(node):
while node != None:
node.next = last_first(node.next)
node = node.next
if node:
node = node.next
def print_list(n):
a = []
while n != None:
a.append(n.data)
n = n.next
print('->'.join([str(d) for d in a]))
public class SingleLinkedList {
private String value;
private SingleLinkedList next;
public SingleLinkedList(String value, SingleLinkedList next){
this.value = value;
this.next = next;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public SingleLinkedList getNext() {
return next;
}
public void setNext(SingleLinkedList next) {
this.next = next;
}
}
public class ListOperations {
/* print the single linked list */
private void printLinkedlist(SingleLinkedList root){
while(root!=null){
System.out.println(root.getValue());
root= root.getNext();
}
}
/* reverse a linked list */
private SingleLinkedList reverseLinkedList(SingleLinkedList root){
SingleLinkedList prev = null;
SingleLinkedList current = root;
SingleLinkedList next = null;
while (current !=null){
next = current.getNext();
current.setNext(prev);
prev = current;
current = next;
}
return prev;
}
/* get middle node */
private SingleLinkedList getMiddleNode(SingleLinkedList root){
SingleLinkedList fast = root;
SingleLinkedList slow = root;
while(fast !=null && fast.getNext()!=null && fast.getNext().getNext()!= null){
fast = fast.getNext().getNext();
slow = slow.getNext();
}
return slow;
}
/*Given a singly linked list: 1->2->3->4->5
Change it to 1->5->2->4->3 using O(1) space*/
private SingleLinkedList shuffleLinkedList(SingleLinkedList root){
SingleLinkedList middle = getMiddleNode(root);
/* get location of middle element */
if (middle !=null) {
//reverse the list after middle position
SingleLinkedList secondList = reverseLinkedList(middle.getNext());
// get the linked list till middle
middle.setNext(null);
SingleLinkedList firstList = root;
// merge first and second list
SingleLinkedList shuffledRoot = firstList;
SingleLinkedList shuffledPtr = null;
boolean fromFirst = true;
SingleLinkedList firstPtr = firstList;
SingleLinkedList secondPtr = secondList;
while (firstPtr != null && secondPtr!=null){
if (fromFirst){
if (shuffledPtr == null){
shuffledPtr = firstList;
firstPtr = firstPtr.getNext();
}
else {
shuffledPtr.setNext(firstPtr);
shuffledPtr = shuffledPtr.getNext();
firstPtr = firstPtr.getNext();
}
}
else {
shuffledPtr.setNext(secondPtr);
shuffledPtr = shuffledPtr.getNext();
secondPtr = secondPtr.getNext();
}
fromFirst = !fromFirst;
}
if (firstPtr == null){
shuffledPtr.setNext(secondPtr);
}
else if(secondPtr == null){
shuffledPtr.setNext(firstPtr);
}
return shuffledRoot;
}
else {
return root;
}
}
public static void main(String args[]){
SingleLinkedList lastNode = new SingleLinkedList("5", null);
SingleLinkedList singleLinkedList = new SingleLinkedList("4", lastNode);
singleLinkedList = new SingleLinkedList("3", singleLinkedList);
singleLinkedList = new SingleLinkedList("2", singleLinkedList);
SingleLinkedList root = new SingleLinkedList("1", singleLinkedList);
ListOperations listOperations = new ListOperations();
//listOperations.printLinkedlist(root);
SingleLinkedList shuffledroot = listOperations.shuffleLinkedList(root);
System.out.println("Shuffled list is ->");
listOperations.printLinkedlist(shuffledroot);
}
}
public class Node {
//data members
int inp_val;
Node next;
//constructor
public Node(int inpval){
this.inp_val=inpval;
this.next=null;
}
}
public class FbLL {
//data members
inp_val inp_val;
int size;
//Construct
public FbLL(Node inpval){
this.inp_val=inpval;
this.size = 1;
}
// add new Node
public void addCar(Node newnode){
Node temp = inp_val;
while (temp.next != null) {
temp=temp.next;
}
temp.next=newnode;
this.size++;
}
// pop a node
public int pop(int idx){
Node temp=inp_val;
for (int i=1; i <idx-1; i++){
temp=temp.next;
}
Node temp2=temp.next;
temp.next=temp.next.next;
return temp2.inp_val;
this.size—;
}
// plug a node
public void plug(int val, int idx){
Node temp=inp_val;
for (int i=1; i <idx-1; i++){
temp=temp.next;
}
Node temp2=temp.next;
temp.next=new Node(val);
temp.next.next=temp2;
this.size++;
}
}
public class main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Node first = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
Node fifth = new Node(5);
FbLL myll = new FbLL(first);
myll.add(second);
myll.add(third);
myll.add(fourth);
myll.add(fifth);
System.out.println("before shuffle");
System.out.println(myll.head.inp_val);
System.out.println(myll.head.next.inp_val);
System.out.println(myll.head.next.next.inp_val);
System.out.println(myll.head.next.next.next.inp_val);
System.out.println(myll.head.next.next.next.next.inp_val);
int val = myll.pop(4);
myll.plug(val, 2);
val = myll.pop(4);
myll.plug(val, 5);
System.out.println("after shuffle");
System.out.println(myll.head.inp_val);
System.out.println(myll.head.next.inp_val);
System.out.println(myll.head.next.next.inp_val);
System.out.println(myll.head.next.next.next.inp_val);
System.out.println(myll.head.next.next.next.next.inp_val);
}
}
Use methods
add : to add a node at the end of linked list
pop : to remove node from desire index and return int
plug : to add new node at desired index
public class Node {
//data members
int inp_val;
Node next;
//constructor
public Node(int inpval){
this.inp_val=inpval;
this.next=null;
}
}
public class FbLL {
//data members
inp_val inp_val;
int size;
//Construct
public FbLL(Node inpval){
this.inp_val=inpval;
this.size = 1;
}
// add new Node
public void addCar(Node newnode){
Node temp = inp_val;
while (temp.next != null) {
temp=temp.next;
}
temp.next=newnode;
this.size++;
}
// pop a node
public int pop(int idx){
Node temp=inp_val;
for (int i=1; i <idx-1; i++){
temp=temp.next;
}
Node temp2=temp.next;
temp.next=temp.next.next;
return temp2.inp_val;
this.size—;
}
// plug a node
public void plug(int val, int idx){
Node temp=inp_val;
for (int i=1; i <idx-1; i++){
temp=temp.next;
}
Node temp2=temp.next;
temp.next=new Node(val);
temp.next.next=temp2;
this.size++;
}
}
public class main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Node first = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
Node fifth = new Node(5);
FbLL myll = new FbLL(first);
myll.add(second);
myll.add(third);
myll.add(fourth);
myll.add(fifth);
System.out.println("before shuffle");
System.out.println(myll.head.inp_val);
System.out.println(myll.head.next.inp_val);
System.out.println(myll.head.next.next.inp_val);
System.out.println(myll.head.next.next.next.inp_val);
System.out.println(myll.head.next.next.next.next.inp_val);
int val = myll.pop(4);
myll.plug(val, 2);
val = myll.pop(4);
myll.plug(val, 5);
System.out.println("after shuffle");
System.out.println(myll.head.inp_val);
System.out.println(myll.head.next.inp_val);
System.out.println(myll.head.next.next.inp_val);
System.out.println(myll.head.next.next.next.inp_val);
System.out.println(myll.head.next.next.next.next.inp_val);
}
}
We can solve this in o(n) using a global pointer and recursion. Initially let the global pointer point to head. Recursively (important ) iterate through the Linked List and during return calls (which will be automatically in reverse order) append the current node to the Node referred by global pointer. Incrremant the Global pointer twice.Do this until the current node and global pointer are same. Although, because of recursion the space used is not O(1).
//globals
private static Node cur;
private static boolean solved=false;
//recursive method
private static void solve(Node root){
if(root.next!=null)
solve(root.next);
if(root!=cur && !solved){
Node tmp=cur.next;
cur.next=root;
root.next=tmp;
cur=cur.next.next;
}else{
cur.next=null;
solved=true;
}
}
Pseudo logic:
Node * specialLinkedList(Node * head)
{
if (!head || !head->next || !head->next->next)
return NULL;
/* Atleast 3 nodes, so middlePoint will not be NULL */
Node* middlePoint=findMiddlePoint(head);
Node* reversedSecondHalf= reverseList(middlePoint->next);
middlePoint->next=NULL;
return mergeList(head, reversedSecondHalf);
Node * specialLinkedList(Node * head)
{
if (!head || !head->next || !head->next->next)
return NULL;
/* Atleast 3 nodes, so middlePoint will not be NULL */
Node* middlePoint=findMiddlePoint(head);
Node* reversedSecondHalf= reverseList(middlePoint->next);
middlePoint->next=NULL;
return mergeList(head, reversedSecondHalf);
#include <iostream>
using namespace std;
class listNode
{
friend class linkedList;
public:
listNode(int data)
:val(data), next(nullptr)
{
}
int getVal()
{
return val;
}
listNode * getNext()
{
return next;
}
private:
int val;
listNode * next;
};
class linkedList
{
public:
linkedList()
:head(nullptr), tail(nullptr)
{
}
void insertAtFront(int val);
void print();
void insertAtEnd(int val);
void removeFromFront();
void removeFromEnd();
listNode * head;
listNode * tail;
};
void linkedList::print()
{
listNode * tmp = head;
while(tmp != nullptr)
{
cout << tmp->val << " " ;
tmp = tmp->next;
}
}
void linkedList::insertAtFront(int val)
{
listNode * tmp = new listNode(val);
if(head == nullptr)
head = tail = tmp;
else
{
listNode * dummy = head;
tmp->next = head;
head = tmp;
}
}
void linkedList::insertAtEnd(int val)
{
listNode * tmp = new listNode(val);
if(tail == nullptr)
head = tail = tmp;
else
{
listNode * dummy = tail;
dummy->next = tmp;
tail = dummy->next;
}
}
void linkedList::removeFromFront()
{
listNode * tmp = head;
if(tmp != nullptr)
{
head = tmp->next;
delete tmp;
}
}
void linkedList::removeFromEnd()
{
listNode * tmp = tail;
if(head == tail)
head = tail = nullptr;
else
{
listNode *currentPtr = head;
while ( currentPtr->next != tail )
currentPtr = currentPtr->next;
tail = currentPtr;
currentPtr->next = nullptr;
}
}
void main()
{
linkedList* myList = new linkedList();
myList->insertAtFront(5);
myList->insertAtFront(4);
myList->insertAtFront(3);
myList->insertAtFront(2);
myList->insertAtFront(1);
myList->print();
cout <<endl;
linkedList* myList2 = new linkedList();
while(myList->head != myList->tail)
{
myList2->insertAtEnd(myList->head->getVal());
myList2->insertAtEnd(myList->tail->getVal());
myList->removeFromFront();
myList->removeFromEnd();
}
myList2->insertAtEnd(myList->head->getVal());
myList2->print();
}
#include <iostream>
using namespace std;
class listNode
{
friend class linkedList;
public:
listNode(int data)
:val(data), next(nullptr)
{
}
int getVal()
{
return val;
}
listNode * getNext()
{
return next;
}
private:
int val;
listNode * next;
};
class linkedList
{
public:
linkedList()
:head(nullptr), tail(nullptr)
{
}
void insertAtFront(int val);
void print();
void insertAtEnd(int val);
void removeFromFront();
void removeFromEnd();
listNode * head;
listNode * tail;
};
void linkedList::print()
{
listNode * tmp = head;
while(tmp != nullptr)
{
cout << tmp->val << " " ;
tmp = tmp->next;
}
}
void linkedList::insertAtFront(int val)
{
listNode * tmp = new listNode(val);
if(head == nullptr)
head = tail = tmp;
else
{
listNode * dummy = head;
tmp->next = head;
head = tmp;
}
}
void linkedList::insertAtEnd(int val)
{
listNode * tmp = new listNode(val);
if(tail == nullptr)
head = tail = tmp;
else
{
listNode * dummy = tail;
dummy->next = tmp;
tail = dummy->next;
}
}
void linkedList::removeFromFront()
{
listNode * tmp = head;
if(tmp != nullptr)
{
head = tmp->next;
delete tmp;
}
}
void linkedList::removeFromEnd()
{
listNode * tmp = tail;
if(head == tail)
head = tail = nullptr;
else
{
listNode *currentPtr = head;
while ( currentPtr->next != tail )
currentPtr = currentPtr->next;
tail = currentPtr;
currentPtr->next = nullptr;
}
}
void main()
{
linkedList* myList = new linkedList();
myList->insertAtFront(5);
myList->insertAtFront(4);
myList->insertAtFront(3);
myList->insertAtFront(2);
myList->insertAtFront(1);
myList->print();
cout <<endl;
linkedList* myList2 = new linkedList();
while(myList->head != myList->tail)
{
myList2->insertAtEnd(myList->head->getVal());
myList2->insertAtEnd(myList->tail->getVal());
myList->removeFromFront();
myList->removeFromEnd();
}
myList2->insertAtEnd(myList->head->getVal());
myList2->print();
}
Simple iterative solution running in O(n^2): constantly go looking for the last node in the list, delete references to it, and insert it next to the current node, until reaching the end of the list (move forward two nodes on each iteration).
public void modifyList(Node head) {
if (head == null || head.next == null) return;
Node current = head;
while (current != null && current.next != null) {
Node last = poll(current);
Node next = current.next;
current.next = last;
current.next.next = next;
current = current.next.next;
}
}
public Node poll(Node head) {
if (head == null) return null;
if (head.next == null) return head;
Node runner = head;
while (runner.next.next != null) {
runner = runner.next;
}
Node last = runner.next;
runner.next = null;
return last;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp
{
class sample
{
static void Main(string[] args)
{
var c = new CLinkedList();
for (int i = 0; i < 10; i++)
c.Add(i);
// Console.WriteLine(c[3]);
Console.Write(c);
Console.ReadKey();
}
}
class Node
{
public Node(int data)
{
this.data = data;
this.Next = null;
}
public int data;
public Node Next;
public override string ToString()
{
return this.data.ToString();
}
}
class CLinkedList
{
public Node head;
public void Add(int data)
{
if (head == null)
{
head = new Node(data);
}
else
{
Node temp = head;
while (temp.Next != null)
{
temp = temp.Next;
}
temp.Next = new Node(data);
}
}
public Node this[int index]
{
get
{
int i = 0;
Node temp = head;
while (i < index && head != null)
{
i++;
temp = temp.Next;
}
return temp;
}
}
public int Length
{
get
{
Node temp = head;
int i = 0;
while (temp != null)
{
temp = temp.Next;
i++;
}
return i;
}
}
public override string ToString()
{
StringBuilder str = new StringBuilder();
for (int i = 0; i < Length/2; i++)
{
str.Append(this[i].data + "," + this[Length-i-1].data + " ," );
}
return str.ToString();
}
}
}
Simple O(n) solution in C#
void processLinkedList<T>(listnode<T> head)
{
if (head == null)
return;
var slow = head;
var fast = head.next;
// find middle list node
while(fast != null)
{
slow = slow.next;
fast = fast?.next?.next;
}
var middle = slow;
listnode<T> prev = null;
// reverse list starting from middle node
while (middle != null)
{
var tmp = middle.next;
middle.next = prev;
prev = middle;
middle = tmp;
}
middle = prev;
// join two lists
while (head != null && middle != null)
{
var list1next = head.next;
var list2next = middle.next;
if (head != middle)
head.next = middle;
if (middle != list1next)
middle.next = list1next;
head = list1next;
middle = list2next;
}
}
void processLinkedList<T>(listnode<T> head)
{
if (head == null)
return;
var slow = head;
var fast = head.next;
// find middle list node
while(fast != null)
{
slow = slow.next;
fast = fast?.next?.next;
}
var middle = slow;
listnode<T> prev = null;
// reverse list starting from middle node
while (middle != null)
{
var tmp = middle.next;
middle.next = prev;
prev = middle;
middle = tmp;
}
middle = prev;
// join two lists
while (head != null && middle != null)
{
var list1next = head.next;
var list2next = middle.next;
if (head != middle)
head.next = middle;
if (middle != list1next)
middle.next = list1next;
head = list1next;
middle = list2next;
}
}
public class UpdateList
{
public static void main(String[] args)
{
node head = new node(1);
node nOne = new node(2);
node nTwo = new node(3);
node nThree = new node(4);
node nfour = new node(5);
head.add(nOne);
nOne.add(nTwo);
nTwo.add(nThree);
nThree.add(nfour);
System.out.print("inital list: ");
node current = head;
while(current != null){
System.out.print(current.getVal());
if(current.getNext() != null){
System.out.print(" -> ");
}
current = current.getNext();
}
System.out.println();
head = reOrderList(head);
System.out.print("final list: ");
current = head;
while(current != null){
System.out.print(current.getVal());
if(current.getNext() != null){
System.out.print(" -> ");
}
current = current.getNext();
}
}
public static node reOrderList(node head){
node walker = head;
node runner = head;
// move walker to the middle of the list
while(walker.getNext() != null && runner.getNext() != null && runner.getNext().getNext() != null){
walker = walker.getNext();
runner = runner.getNext().getNext();
}
// set up nodes to reverse back half of list
node currentNode = walker;
node previousNode = null;
node nextNode = null;
// point walker to next element in halfway list
walker = walker.getNext();
// reverse list at midway point
while(currentNode != null){
nextNode = currentNode.getNext();
currentNode.add(previousNode);
previousNode = currentNode;
currentNode = nextNode;
}
// add reversed list to original list, swaping the first element of the reversed list
// with the last element of the original (non revsersed) list
node endOfOriginalList = head.getNext();
head.add(runner);
runner.add(endOfOriginalList);
endOfOriginalList.add(walker);
return head;
}
}
public class node{
private node next;
private int val;
public node(int val){
this.next = null;
this.val = val;
}
public void add(node n){
this.next = n;
}
public node getNext(){
return this.next;
}
public int getVal(){
return this.val;
}
}
public List<Node> interleave(List<Node> list) {
if (list == null) return null;
// find center of the list
Node center = findCenter(list);
// reverse the second half
Node reversed = reverse(center.next);
center.next = null;
// interleave
Node fTemp = list, nfTemp = list.next, rTemp = reversed, nrTemp;
while (fTemp != null || rTemp != null) {
nfTemp = fTemp.next;
rfTemp = rTemp.next
fTemp.next = rTemp;
rTemp.next = nfTemp;
rTemp = nrTemp;
fTemp = nfTemp;
}
return list;
}
private List<Node> findCenter(List<Node> list) {
if (list == null) return null;
Node n = list;
Node 2n = n.next;
while (2n != null && 2n.next != null) {
n = n.next;
2n = 2n.next.next;
}
return n;
}
private List<Node> reverse(List<Node> list) {
if (list == null) return null;
Node first = list, second = first.next, third;
first.next = null;
while (second != null) {
second.next = first;
first = second;
second = third;
third = (second != null) ? second.next : null;
}
return first;
}
class LL_Node {
public int data;
public LL_Node next;
LL_Node(int d) {
data = d;
}
}
public class FacebookLLChange {
static void printLL(LL_Node head) {
while (head != null) {
System.out.print(head.data+"->");
head = head.next;
}
System.out.println("null");
}
static LL_Node rearrangeLL(LL_Node head) {
LL_Node curr = head;
LL_Node temp1, temp2;
// Start by removing "5" and inserting it in between "1" and "2"
while (curr.next.next != null) {
curr = curr.next;
}
temp1 = curr.next; // 5->null
curr.next = null;
curr = head;
temp2 = curr.next; // 2->3->4->null
curr.next = temp1;
curr.next.next = temp2;
// Similarly, remove "4" and insert it between "2" and "3"
while (curr.next.next != null) {
curr = curr.next;
}
temp1 = curr.next; // 4->null
curr.next = null;
curr = head.next.next;
temp2 = curr.next; // 3->null
curr.next = temp1;
curr.next.next = temp2;
return head;
}
public static void main(String[] args) {
// Load all elements on new Linked List
LL_Node head = new LL_Node(1);
LL_Node curr = head;
for (int i = 1; i < 5; i++) {
curr.next = new LL_Node(i+1);
curr = curr.next;
}
System.out.println("Before change: ");
printLL(head); // 1->2->3->4->5->null
// Change Linked List without any O(n) sized buffers
head = rearrangeLL(head);
System.out.println("After change: ");
printLL(head); // 1->5->2->4->3->null
}
}
Firstly, use slow and fast point to get the middle point;
- cherrytino91 December 10, 2016Secondly, reverse the list after the middle point;
Finally, merge the the init linked list and the reversed linked list.