Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

public Node swapApp(Node node) {
Deque<Node> stack = new ArrayDeque<>();
while (node != null) {
node = node.next;
}
Node head = new Node('Z');
Node dummy = head;
boolean isAlternate = true;
while (!stack.isEmpty()) {
Node n1 = null;
if (isAlternate) {
n1 = stack.pollLast();
} else {
n1 = stack.pollFirst();
}
n1.next = null;
isAlternate = !isAlternate;
}

return dummy.next;
}

Comment hidden because of low score. Click to expand.
0

It should be in memory . No extra space is allowed .

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

If you are using it already, why don't we use arraylist and simply solve the problem there by storing pointers and then reorder the list? :-)

Comment hidden because of low score. Click to expand.
1
of 1 vote

Leetcode 143. Reorder List

Comment hidden because of low score. Click to expand.
1
of 1 vote

/**
* 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) {

// 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
}

// 3. merge mid and head
let currMid = newHead

while (currHead && currMid) {
const midNext = currMid.next

currMid = midNext
}

};

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you give more specification about the question?

Comment hidden because of low score. Click to expand.
0
of 0 vote

step 0: A->B->C->D->E
step 1: A->B->C<-D<-E
step 2: A->E, B->C<-D
step 3: A->E->B->D, C
step 4: A->E->B->D->C

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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.RemoveLast();
}

foreach (var element in list)
{
Console.Write(string.Concat(element, " "));
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

use the same recursion as checking palindrome of linked list. play around with pointers when rewinding and you will be able to solve it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
ListNode left=null;

public void reorderList(ListNode 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;

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
ListNode left=null;
public void reorderList(ListNode 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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
ListNode left=null;

public void reorderList(ListNode 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;

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
ListNode left=null;

public void reorderList(ListNode 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;

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Inplace through recusion

class Solution {
public void reorderList(ListNode head) {
}

private ListNode reorder(ListNode slow, ListNode fast) {
if (fast == null) {
return slow;
}
if (fast.next == null) {
ListNode toRet = slow.next;
slow.next = null;
}
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;
}
}Solution {
public void reorderList(ListNode head) {
}

private ListNode reorder(ListNode slow, ListNode fast) {
if (fast == null) {
return slow;
}
if (fast.next == null) {
ListNode toRet = slow.next;
slow.next = null;
}
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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

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) {
}

private ListNode reorder(ListNode slow, ListNode fast) {
if (fast == null) {
return slow;
}
if (fast.next == null) {
ListNode toRet = slow.next;
slow.next = null;
}
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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

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) {
}

private ListNode reorder(ListNode slow, ListNode fast) {
if (fast == null) {
return slow;
}
if (fast.next == null) {
ListNode toRet = slow.next;
slow.next = null;
}
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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

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) {
}

private ListNode reorder(ListNode slow, ListNode fast) {
if (fast == null) {
return slow;
}
if (fast.next == null) {
ListNode toRet = slow.next;
slow.next = null;
}
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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public void reorderList()
{
FBNode current = head, c2 = head;
FBNode next = null, prev = null;
while (current.next != null)
{
next = current.next;
while (c2.next != null)
{
prev = c2;
c2 = c2.next;
}
prev.next = null;
current.next = c2;
c2.next = next;
c2 = next;
current = next;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is recursive python implementation

class Node:
def __init__(self,val):
self.val = val
self.next = None

def __repr__(self):
string = ""
string += str(head.val) + ','
return string

class Llist:
def __init__(self):
self.tail = None
def insert(self, val):
node = Node(val)
self.tail = self.head = node
else:
self.tail.next = node
self.tail = node
return True

def __repr__(self):
string = ""
string += str(head.val) + ','
return string

if not flag:
if not temp:
if temp:

else:
flag=False
flag=False

llist1 = Llist()
llist1.insert('A')
llist1.insert('B')
llist1.insert('C')
llist1.insert('D')
llist1.insert('E')
llist1.insert('F')
print(llist1)
flag = True

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
def __init__(self,val):
self.val = val
self.next = None

def __repr__(self):
string = ""
string += str(head.val) + ','
return string

class Llist:
def __init__(self):
self.tail = None
def insert(self, val):
node = Node(val)
self.tail = self.head = node
else:
self.tail.next = node
self.tail = node
return True

def __repr__(self):
string = ""
string += str(head.val) + ','
return string

if not flag:
if not temp:
if temp:

else:
flag=False
flag=False

llist1 = Llist()
llist1.insert('A')
llist1.insert('B')
llist1.insert('C')
llist1.insert('D')
llist1.insert('E')
llist1.insert('F')
print(llist1)
flag = True

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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
}
}

constructor() {
this.tail = null;
this.length = 0;
}

let node = new Node(data)

}

if (this.tail) {
this.tail.next = node
node.previous = this.tail
}

this.tail = node

this.length++
}

get(index) {
return null

if (index <= 0)

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.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--

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()

for (let i = 1; i < list.length-2; i++) {
list.switch(i, list.length)
list.print()
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

ListNode* oddEvenList(ListNode* head) {

int i=0;
ListNode* oddlist = nullptr;
ListNode* evenlist = nullptr;
ListNode* cur = head;
ListNode* oddhead = nullptr;
while (cur) {
if (i%2 == 1) {
if (!oddlist)
else
oddlist->next = cur;
oddlist = cur;
} else {
if (evenlist)
evenlist->next = cur;
evenlist = cur;
}
cur = cur->next;
i++;
}
if (oddlist)
oddlist->next = nullptr;
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.