Facebook Interview Question
Country: United States
Good solution, except the end should be:
head = prev
since prev would be pointing to the head of the linked-list at this point (current would be pointing to null in order to escape the while loop).
Do you even need three pointers? Couldn't you just adjust the original head as you go, and then pass back the new head? Like so:
node* reverse_node(node* head){
node *previous = NULL;
while (head->next) {
node *current = head;
head = head->next;
current->next = previous;
previous = current;
}
head->next = previous;
return head;
}
Do you even need three pointers? Couldn't you just adjust the original head as you go, and then pass back the new head? Like so:
node* reverse_node(node* head){
node *previous = NULL;
while (head->next) {
node *current = head;
head = head->next;
current->next = previous;
previous = current;
}
head->next = previous;
return head;
}
When current is at the last node, previous is at last but one node, and next will be pointing to null
So,
current -> next = previous; //will point the last node to last but one.
previous = current; //previous is at last node
current = next node; //current is null
next node = current.next(); // Null pointer exception.
ListNode reverse(ListNode head) {
ListNode p = head;
if (p.next != null) {
head = reverse(p.next);
p.next.next = p;
p.next = null;
}
return head;
}
I guess that asking this type of question the interviewer wants us to work us with singly linked list. One can use two pointers 'head' and 'tail' pointing to a head and tail of the linked list. Then the process would be (i) link tail.next to head and (ii) update head, update tail, (iii) set tail.next to null to avoid circular list. A sample code is shown below:
public void reverseList(Node list) {
if (list == null || list.next == null) return;
int N=1;
Node head = list;
Node tail = list;
while(tail.next != null) { // get tail and list length
N++;
tail = tail.next;
}
for (int k = 0; k < N-1; k++) {
tail.next = head;
head = head.next;
tail = tail.next;
tail.next = null;
}
list = head;
}
public class Node {
public Node next;
public int val;
}
#include <iostream>
class Node
{
public:
Node(int nValue): nValue(nValue), pNext(0)
{};
Node(int nValue, Node *pNext): nValue(nValue), pNext(pNext)
{};
int nValue;
Node *pNext;
};
void PrintList(Node *pNode)
{
while (pNode)
{
std::cout << pNode->nValue << std::endl;
pNode = pNode->pNext;
}
}
void ReverseList(Node *pNode)
{
Node *pCurrent = 0;
Node *pNext = 0;
while (pNode)
{
// Storing the next of current node
pNext = pNode->pNext;
// If current was already set, it means it's not the first node -> we need to change the node->next to current (which is actually previous node)
if (pCurrent)
{
pNode->pNext = pCurrent;
}
else
{
// In this case, this is first node
pNode->pNext = 0;
}
pCurrent = pNode;
pNode = pNext;
}
}
int main(int argc, const char * argv[]) {
Node *a = new Node(1);
Node *b = new Node(2, a);
Node *c = new Node(3, b);
Node *d = new Node(4, c);
// Print list before
std::cout << "From D:" << std::endl;
PrintList(d);
std::cout << "From A:" << std::endl;
PrintList(a);
// Reverse linked list in O(1) memory
ReverseList(d);
// Print list after
std::cout << "From D:" << std::endl;
PrintList(d);
std::cout << "From A:" << std::endl;
PrintList(a);
delete d;
delete c;
delete b;
delete a;
return 0;
}
#include <iostream>
class Node
{
public:
Node(int nValue): nValue(nValue), pNext(0)
{};
Node(int nValue, Node *pNext): nValue(nValue), pNext(pNext)
{};
int nValue;
Node *pNext;
};
void PrintList(Node *pNode)
{
while (pNode)
{
std::cout << pNode->nValue << std::endl;
pNode = pNode->pNext;
}
}
void ReverseList(Node *pNode)
{
Node *pCurrent = 0;
Node *pNext = 0;
while (pNode)
{
// Storing the next of current node
pNext = pNode->pNext;
// If current was already set, it means it's not the first node -> we need to change the node->next to current (which is actually previous node)
if (pCurrent)
{
pNode->pNext = pCurrent;
}
else
{
// In this case, this is first node
pNode->pNext = 0;
}
pCurrent = pNode;
pNode = pNext;
}
}
int main(int argc, const char * argv[]) {
Node *a = new Node(1);
Node *b = new Node(2, a);
Node *c = new Node(3, b);
Node *d = new Node(4, c);
// Print list before
std::cout << "From D:" << std::endl;
PrintList(d);
std::cout << "From A:" << std::endl;
PrintList(a);
// Reverse linked list in O(1) memory
ReverseList(d);
// Print list after
std::cout << "From D:" << std::endl;
PrintList(d);
std::cout << "From A:" << std::endl;
PrintList(a);
delete d;
delete c;
delete b;
delete a;
return 0;
}
Public SingleNode reverse(SingleNode head){
If ( head == null) return head;
SingleNode current = head;
SingleNode prev = null;
While (current != null){
SingleNode next = current.next;
current.next = prev;
// Assign prev to itself
prev = current;
// Make the next current
current = next;
}
return prev;
}
This one use recursion. I know I know. just for the fun of it (untested)
node* reverse(node** head)
{
if (head == null || head->next == null)
return head;
node* current = head;
node* rest = head->next;
second = reverse(&rest);
current->next->next = current;
current->next = null;
&head = rest;
return current;
}
public static Node ReverseList(Node head)
{
if(head == null)
return null;
ReverseListHelper(head.Next, head);
}
private static Node ReverseListHelper(Node current, Node head)
{
if(current == null)
return null;
if(current.Next == null)
{
head.Next = current;
}
else
{
Node n = ReverseListHelper(current.Next, head);
n.Next = current;
}
return current;
}
class ReverseLinkedList {
public void reverse() {
head = reverseRec(head, null);
}
public Node reverseRec(Node current, Node reverse) {
if (current == null) return reverse;
Node next = current.getNext();
current.setNext(reverse);
reverse = current;
current = next;
return reverseRec(current, reverse);
}
}
Python, O(n), employs 3 pointers to implement LL.reverse()
a is the "previous"
b is the "current"
c is the "next"
class node:
data = None
nxt = None
class LL:
head = None
def __init__(self):
self.head = node()
self.head.nxt = node()
def insert(self, data):
n = node()
n.data = data
tmp = self.head
while tmp.nxt.data != None:
tmp = tmp.nxt
tmp.nxt = n
# end with sentinel node; last node has data = None
tmp = tmp.nxt
sentinal = node()
tmp.nxt = sentinal
def printer(self):
tmp = self.head
while tmp.nxt.data != None:
tmp = tmp.nxt
print tmp.data
def reverse(self): # needs 3 helping pointers to reverse
a = self.head
b = a.nxt
c = a.nxt.nxt
while True:
b.nxt = a
a = b
b = c
if c.data == None: # we're at last element;
c.nxt = a # point back to second last
break
c = c.nxt
self.head.nxt = None # turns head into sentinal node
self.head = c # assign head to point at last element of LL
if __name__ == '__main__':
l = LL()
l.insert(5)
l.insert(1)
l.insert(3)
l.insert(9)
l.insert(7)
l.printer()
l.reverse()
l.printer()
I'm assuming an empty first head node.
public static void ReverseList(Node head)
{
if(head == null)
{
return;
}
head = CoreReverseList(head.Next, null);
}
private static Node CoreReverseList(Node cur, Node prev)
{
if(cur == null)
return prev;
Node n = CoreReverseList(cur.Next, cur);
cur.Next = prev;
return n;
}
public static void reverseLinkedList(LinkedList L1){
LinkedListNode second = L1.head.next;
LinkedListNode Third = second.next;
second.next=L1.head;
L1.head.next=null;
LinkedListNode previous = second;
LinkedListNode current= Third;
while(current!=null){
LinkedListNode nextNode=current.next;
current.next=previous;
previous=current;
current=nextNode;
}
L1.head=previous;
}
None of the answers here truly used O(1) space. The intention of the interviewer was to see if the candidate was able to use recursion (and internal stack space) to get this done. The O(1) space was to store the new head.
public class HelloWorld{
public static void main(String []args){
System.out.println("Hello World");
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
n1.next = n2;
n2.next = n3;
n3.next = n4;
printList(n1);
printList(reverseListHelper(n1));
}
public static Node reverseListHelper(Node head) {
Node startNode = head;
while (head.next != null) {
head = head.next;
}
System.out.println(startNode.data + " ");
System.out.println(head.data + " ");
reverseList(startNode);
return head;
}
public static Node reverseList(Node node) {
if(node.next!=null) {
Node n = reverseList(node.next);
n.next = node;
node.next = null;
return node;
} else {
return node;
}
}
public static void printList(Node root) {
if(root == null) return;
System.out.println();
while(root!=null) {
System.out.print(root.data + "->");
root = root.next;
}
System.out.println();
}
}
None of the answers here truly used O(1) space. The intention of the interviewer was to see if the candidate was able to use recursion (and internal stack space) to get this done. The O(1) space was to store the new head.
public class HelloWorld{
public static void main(String []args){
System.out.println("Hello World");
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
n1.next = n2;
n2.next = n3;
n3.next = n4;
printList(n1);
printList(reverseListHelper(n1));
}
public static Node reverseListHelper(Node head) {
Node startNode = head;
while (head.next != null) {
head = head.next;
}
System.out.println(startNode.data + " ");
System.out.println(head.data + " ");
reverseList(startNode);
return head;
}
public static Node reverseList(Node node) {
if(node.next!=null) {
Node n = reverseList(node.next);
n.next = node;
node.next = null;
return node;
} else {
return node;
}
}
public static void printList(Node root) {
if(root == null) return;
System.out.println();
while(root!=null) {
System.out.print(root.data + "->");
root = root.next;
}
System.out.println();
}
}
None of the answers here truly used O(1) space. The intention of the interviewer was to see if the candidate was able to use recursion (and internal stack space) to get this done. The O(1) space was to store the new head.
public class HelloWorld{
public static void main(String []args){
System.out.println("Hello World");
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
n1.next = n2;
n2.next = n3;
n3.next = n4;
printList(n1);
printList(reverseListHelper(n1));
}
public static Node reverseListHelper(Node head) {
Node startNode = head;
while (head.next != null) {
head = head.next;
}
System.out.println(startNode.data + " ");
System.out.println(head.data + " ");
reverseList(startNode);
return head;
}
public static Node reverseList(Node node) {
if(node.next!=null) {
Node n = reverseList(node.next);
n.next = node;
node.next = null;
return node;
} else {
return node;
}
}
public static void printList(Node root) {
if(root == null) return;
System.out.println();
while(root!=null) {
System.out.print(root.data + "->");
root = root.next;
}
System.out.println();
}
}
Here is C++ version of solution. Space complexity is O(1).
#include<iostream>
using namespace std;
struct node {
int v;
node * next;
node(int value):v(value), next(0){}
};
node * reverse(node * s)
{
node *prev=0, *cur =s, *next = 0;
while(cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
Idea: use 3 nodes, traverse down the list and redirect all "next" pointer to previous object in list
Time: O(n)
Storage: O(3) = O(1)
I think I might have missed some checking on whether it's breaking the loop at some speciall cases, but the idea should be right
- Henry February 24, 2015void Reverse(node* head) { node* previous = null; node* current = head; node* next_node = current ->next; while( !current ) { current->next = previous; previous = current; current = next_node; next_node = current -> next; } head = current; }