Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
You dont even need to count the number of nodes in linked list... just use the small and fast pointer to find middle
@vik: True. Both approaches are different ways of doing the same thing. I wasn't concerned with optimizing the algorithm as much as possible, but only with giving a reasonable O(n) approach.
Here is a working code.. in case anyone wanna have a look
node* reverseList(node* head){
if (!head) return NULL;
node *curr(head), *prev(NULL), *tmp(NULL),*newHead(NULL);
while (curr){
tmp = curr->next;
curr->next = prev;
prev = curr;
curr = tmp;
}
newHead = prev;
return newHead;
}
node* mergeLastAndFirst(node* head){
if (head==NULL )return NULL;
if (head->next==NULL )return head;
node * curr(NULL), *slow(head), *fast(head);
node *newHead(NULL), *tail(NULL),*tmp(NULL),*prev(NULL);
while (fast && fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
tail = reverseList(slow->next); //slow will always have next
printList(tail);
slow->next = NULL;
newHead = curr = tail;
while(head && tail){
tmp = tail->next;
curr->next = head;
tail = tmp;
head = head->next;
prev = curr->next;
curr->next->next = tail;//->next;
curr = curr->next->next;
}
if (!curr) curr=prev;
if (head) curr->next = head;
if (tail) curr->next = tail;
return newHead;
}
But the question says that the linked list is singly linked list.Each node cannot have reference to previous element.
Below is the working C code for this algorithm:
void RotateFromMiddleSingleLinkedList(node **head)
{
node* middle = FindMiddleofSingleLinkedList(*head);
node *middlenext = reverseSingleLinkedList(middle->next);
middle->next = middlenext;
node *current = middlenext;
node *p = *head;
node *prev = NULL;
while(current)
{
middle->next = current->next;
current->next = p;
if(prev)
prev->next = current;
if(p == *head)
*head = current;
p = p->next;
prev = current->next;
current = middle->next;
}
middle->next = NULL;
}
My Algo goes here
1> Say U have one link list with head as a pointer (Given Link List)
2> Create another link List and reverse it . O(n) + O (n)
3> For each node in any of the list until n is list.length / 2
Create a new list with value one from list 1 and one from list 2
advance the pointer in both list
end of loop
why are you wasting space in creating a extra linked list which is not even needed. this solution can be easily done without any extra space
My algo(using java)
First put all elements into hashmap.
clear the list.
Then start from last element to half of the no of elements.
have a variable which points to first element.
add last and first element ...increment the variables which points to first and last element.
it takes O(n)+o(n/2) time complexity
My approach for this problem is:-
1. create slow and fast pointer go to middle.
2. Reverse the Link list from middle.
If it is 1->2->3>4>5>6>7 Initially then now It will be 1>2>3>4>7>6>5
3. Start from to mid + 1 which is 7 and from head which is 1
4. Then with the help of 2 pointers create pattern like:-
7>1>6>2>5>3>4
No, the list should be singly linked and you cannot create a copy of the list. You should change the pointers of the original list.
func(Node current)
find the mid-point of list -> O(N)
int size=1;
int cnt=1;
Node right = null;
Node temp = current;
Node temptemp=null;
Node left = null;
while(temp.next = null) {
size++;
temp = temp.next
}
temp=current;
/*Now break the list and reverse the second half*/
do {
if(current > size/2){
temptemp=temp.next
temp.next=right;
right=temp;
temp=temptemp;
} else {
temp = temp.next;
}
current++;
}while(temp=null)
/*Merge the list*/
left=current;
current = right;
while(left != null && right != null) {
temp=right.next;
right.next=left;
right=temp;
left=left.next
}
return current
}
Node solve (Node start, int noElements){
Node current=start;
if (noElements==1) return current;
while (current.next!=null){
current=current.next;
}
current.next=start;
start.next=solve(start.next, --noElements);
return current;
}
For the first time in you reach end of the code using
while (current.next!=null){
current=current.next;
}
and it reaches to 7 in list 1-2-3-4-5-6-7
then u call solve(start.next,--noElements) ,
now when it enters while loop
while(current.next!=null) .. this loop never ends as in the previous step you made linklist circular.... ,correct me if im wrong
yes that is a correct observation, the while loop does not terminate because the list becomes circular, however we can use a 'for' loop which loops for 'noElements' times.
node * change(node *head){
if(head==NULL || head->next==NULL) return head;
node * current=head,prev,next,current1;
while(current->next !=NULL){
prev=current;
current=current->next;
}
prev->next=NULL;
current->next=head;
head=current;
current=head->next;
while(current->next !=NULL){
current1=current->next;
while(current1->next !=NULL){
prev= current1;
current1=current1->next;
}
prev->next= NULL;
next=current->next;
current->next=current1;
current1->next=next;
current=next;
}
return head;
}
This is O(N*N) approach
Other approach is we can divide linked list in two parts using two pointer approach
Then reverse the second half and after that simply merge both the linked list :)
Implementation of this algorithm is very easy :)
time complexity :O(N)
If you don't have space limitations, you could use a stack and a queue, traverse the list and insert each element in both structures. While you traverse, you can increment a counter to know the size of the list. Once you've finished traversing, you extract an element of each structure and add it to a new list. You must do it half the counter times.
I think this would be in O(n), wouldn't it?
I've posted the solution that is using stack, it can be found in the very last comment on this page. This solution is O(n) because insert and remove operations in linked list implementation of C# are O(1). However, the same level of complexity can be supported manually with small additions to the same algorithm.
func(Node current)
find the mid-point of list -> O(N)
int size=1;
int cnt=1;
Node right = null;
Node temp = current;
Node temptemp=null;
Node left = null;
while(temp.next = null) {
size++;
temp = temp.next
}
temp=current;
/*Now break the list and reverse the second half*/
do {
if(current > size/2){
temptemp=temp.next
temp.next=right;
right=temp;
temp=temptemp;
} else {
temp = temp.next;
}
current++;
}while(temp=null)
/*Merge the list*/
left=current;
current = right;
while(left != null && right != null) {
temp=right.next;
right.next=left;
right=temp;
left=left.next
}
class ReverseMiddle
{
public:
//1->2->3->4->5->6->7 ==> 7->1->6->2->5->3->4
//1->2->3->4->5->6->7->8 ==> 8->1->7->2->6->3->5->4
static void Go()
{
//Build test case
// Quick & Ugly : initialize the linked list
// If count is not given, traverse O(n) to count
//int nTotal = 7;
int nTotal = 8;
//Node* pList = new Node(1, new Node(2, new Node(3, new Node(4, new Node(5, new Node(6, new Node(7, nullptr)))))));
Node* pList = new Node(1, new Node(2, new Node(3, new Node(4, new Node(5, new Node(6, new Node(7, new Node(8, nullptr))))))));
// Reverse the list from 1 -> nTotal/2
Node* pCurrent = pList;
Node* pPrevious = nullptr;
for(int nIndex = 1; nIndex <= nTotal/2; nIndex++)
{
Node* pNext = pCurrent->m_pNext;
pCurrent->m_pNext = pPrevious;
pPrevious = pCurrent;
pCurrent = pNext;
}
Node* pNextFragment = nullptr;
if(nTotal%2 != 0)
{
// For odd numbered list, preserve the middle element to be placed @ the end!
Node* pNext = pCurrent->m_pNext;
pNextFragment = pCurrent;
pNextFragment->m_pNext = nullptr;
pCurrent = pNext;
}
// Iterate the second half making the correct links
for(int nIndex = 1; nIndex <= nTotal/2; nIndex++)
{
Node* pNext = pCurrent->m_pNext;
Node* pReverseNext = pPrevious->m_pNext;
pCurrent->m_pNext = pPrevious;
pPrevious->m_pNext = pNextFragment;
pNextFragment = pCurrent; // Next fragment points to chain formed so far - base case: if nTotal is even, it's null, if nTotal is odd, it's the middle element
pPrevious = pReverseNext; // pPrevious jumps to next element in the reverse chain of first half
pCurrent = pNext; // pCurrent jumpts to next element in the forward chain of second half
}
// Place the final result in pList !!
pList = pNextFragment;
}
private:
struct Node
{
public:
Node(int nValue, Node* pNext)
: m_nValue(nValue),
m_pNext(pNext)
{
}
int m_nValue;
Node* m_pNext;
};
};
Using fast pointer-slow pointer method, find the middle node. Traverse again from middle to end and store all the node coming in way in a stack. The pointer to first node is already there. Then pop a node from stack and traverse from first node to the middle alternatively rearranging the pointers. There it is!
Another solution in Java. What you guys think about it.
public ListNode doStuff(ListNode head) {
ListNode prev = null;
ListNode start = null;
ListNode lastNowFirst = head;
while (lastNowFirst.next != null) {
lastNowFirst = lastNowFirst.next;
}
boolean flg = false;
while (head != null && head.next != null) {
ListNode last = head;
while (last.next != null) {
prev = last;
last = last.next;
}
prev.next = null;
last.next = head;
if (flg) {
start.next = last;
}
start = head;
head = head.next;
flg = true;
}
return lastNowFirst;
}
No extra space/stack/queue required.
Total time 2n=> O(n)
Simple non recursive solution
1. Use small and fast pointer to find middle of linked list (no need to calculate length and waste n operations) Time = n/2
2. Reverse the part of list which is following the middle(slow after 1st step) pointer (i have used it as tail in my code) Time = n/2
3. Merge the two half lists (head and tail lists) Time = n
Total time= n/2+n/2+n=2n
Your code does spent O(n) to find the middle of the list because fast pointer goes until the end of the list:
while (fast && fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
so 1. is invalid, down voted the answer.
Hi here is the basic function where we can get the o/p.This is the code in C#
public void MergeLinkedList()
{
Node current = first;
ArrayList arr = new ArrayList();
ArrayList mergedarr = new ArrayList();
int count = 0;
int i = 0, j = count;
if (current == null)
arr.Add(null);
else
{
while (current != null)
{
arr.Add(current.Data);
current = current.Next;
count++;
j = count;
}
Console.WriteLine("value of j={0}", j);
}
foreach (int element in arr)
{
Console.WriteLine(element);
}
Console.WriteLine("Merging the linked list");
for (i = 0, j = count - 1; i <= j; )
{
if (i == j)
{
mergedarr.Add(arr[i]);
break;
}
else
{
mergedarr.Add(arr[j]);
mergedarr.Add(arr[i]);
i++;
j--;
}
}
foreach (int element in mergedarr)
{
Console.WriteLine(element);
}
Console.Read();
}
public List<Integer> sort(List<Integer> list){
List<Integer>reverseList = null:
List<Integer> finalList = null;
reverseList = Collections.sort(list, Collections.reverseOrder());
for(int i=0; i < list.length; i++){
if(i%2=0)
finalList.add(reverseList.get(i));
else
finalList.add(list.get(i));
}
return finalList;
}
public class StringMan {
static String sA[] = new String[] {"1", "2", "3", "4", "5", "6", "7"};
public ArrayList crunch(String [] ax){
int n = ax.length;
ArrayList al = new ArrayList();
int maxIter = ax.length / 2;
int extraIter = ax.length % 2;
for(int i = 0; i < maxIter; i++){
al.add(ax[n-(i+1)]);
al.add(i+1);
if(i == maxIter -1 && extraIter > 0){
al.add(i+2);
}
}
return al;
}
public static void main(String [] s){
ArrayList al = new StringMan().crunch(sA);
System.out.println(al);
}
}
struct my_list {
int i;
struct my_list *next;
};
static void
insert_on_list(struct my_list **head, struct my_list **tail, int i)
{
struct my_list *node;
if (!*head)
*head = node = (struct my_list *) malloc(sizeof(struct my_list));
else
(*tail)->next = node = (struct my_list *) malloc(sizeof(struct my_list));
*tail = node;
node->next = NULL;
node->i = i;
}
int
main(int argc, char **argv)
{
struct my_list *head = NULL, *tail = NULL, *node;
for (auto i = 1; i <= 7; ++i)
insert_on_list(&head, &tail, i);
node = head;
std::deque<my_list *> queue;
while (node) {
queue.push_back(node);
node = node->next;
}
node = head = queue.back();
queue.pop_back();
bool even = 1;
while (!queue.empty()) {
if (even) {
tail = node->next = queue.front();
queue.pop_front();
}
else {
tail = node->next = queue.back();
queue.pop_back();
}
node = tail;
even = !even;
}
tail->next = NULL;
node = head;
while (node) {
std::cout << node->i << " ";
node = node->next;
}
std::cout << std::endl;
return 0;
}
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
head = None
node_count = 0
def build_list(self):
for each in xrange(17):
self.insert_node(each)
def insert_node(self,data):
new_node = Node(data)
node = self.head
if node:
while node.next:
node = node.next
node.next = new_node
else:
self.head = new_node
self.node_count+=1
def print_list(self):
node = self.head
while node:
print node.data
node = node.next
def process_list(self,index,node):
top_node = None
if not node:
return None
elif not node.next:
return None
else:
index += 1
top_node = self.process_list(index,node.next)
if not top_node:
top_node = self.head
if index > self.node_count/2-1:
tmp = node.next
if index == self.node_count-1:
node.next = node.next.next
tmp.next = top_node
self.head = tmp
top_node = self.head
else:
node.next = node.next.next
tmp.next = top_node.next
top_node.next = tmp
top_node = tmp
return top_node.next
if __name__ == "__main__":
linked_list = LinkedList()
linked_list.build_list()
linked_list.print_list()
print 'after..'
linked_list.process_list(0,linked_list.head)
linked_list.print_list()
Another one recursive solution in java.
static int num=0;
static Node node1,node2;
public static void fun(Node head){
int cur = 0;
if(num==0){
node1 = head;
}
num++;
cur = num;
if(head.getLinkNode()!=null){
flicker(head.getLinkNode());
}
if(cur>(num+1)/2){
head.setLinkNode(node1);
if (node2!=null){
node2.setLinkNode(head);
}
node2 = node1;
node1 = node1.getLinkNode();
}
else if(cur==(num+1)/2){
head.setLinkNode(null);
}
}
If extra space is allowed, then :
static void ArrangeLinkedList<T>(LinkedList<T> list) where T : IComparable<T>
{
var stack = new Stack<LinkedListNode<T>>();
var current = list.First;
while (current != null)
{
stack.Push(current);
current = current.Next;
}
current = list.First;
while (current!=null && stack.Peek()!=current)
{
var node = stack.Pop();
list.Remove(node);
list.AddBefore(current, node);
current = current.Next;
}
}
May be use stack and queue together , even though i am using array in example below , but the logic will be same for the list .
oriArray = [ 1,2, 3,4,5,6,7]
mystack=[]
myqueue=[]
arrayLength=len(oriArray) #If its a list data structure , we can get the length in loop below
for i in range(0,arrayLength):
myqueue.append(oriArray[i])
mystack.insert(0,oriArray[i])
for i in range(0,len(oriArray)/2):
print mystack.pop(0);
print myqueue.pop(0);
if len(oriArray) %2 != 0 :
print mystack.pop(0)
C# Solution
/* Algorithm:
* For a maximum of (length of list)/2 iterations:
* 1. Maintain position of the element after which
* you want to insert the last element.
* 2. Move last element to the position above.
* 3. Update your marker from step 1 in preparation
* of insertion of the new last element.
*
* Complexity: O(N)
*
* Test Cases:
* - null
* - List of 1 element
* - List of 2 elements
* - List of 3 elements
* - Large list
*/
public static void OrderList(LinkedList<int> head)
{
//If the list is empty or has 1 element, return
if (head == null || head.First.Next == null)
return;
//Last element will be inserted after this position.
LinkedListNode<int> writePtr;
//Will assist in insertion operation.
LinkedListNode<int> temp;
//Find the middle of the list.
int mid = head.Count / 2;
//Move the last element
//to the starting position.
writePtr = head.Last;
head.RemoveLast();
head.AddFirst(writePtr);
//Move the pointer to the second element.
writePtr = head.First.Next;
for(int i = 1 ; i < mid; i++)
{
//remove from the end
temp = head.Last;
head.RemoveLast();
//add after required element.
head.AddAfter(writePtr, temp);
//update the marker to point to the element
//after which you want to add the new last element.
writePtr = writePtr.Next.Next;
}
1) Count the nodes in the list. Then travel half of them to get to the middle of the list
- eugene.yarovoi February 05, 20132) Starting with the middle of the list, use the standard algorithm for reversing a singly-linked list in place until you reach the end of the list.
3) Get a pointer to the node that used to be last node before the reversal (and now is the middle node), call it endPointer. Also get a pointer to the start node of the list, call it startPointer.
4) Take turns advancing the two pointers, printing elements as you go. Like, print startPointer; startPointer = startPointer.next; print endPointer; endPointer = endPointer.next. Do this until the endPointer reaches the null pointer (the end of the list after reversal).
5) Restore the original value of endPointer from step 3, and reverse the linked list from that point until the end (null terminator). This restores the list to its original state.
Of course you have to be careful about how you treat lists of even size vs. lists of odd size and watch out for off-by-one bugs, but these are the basic steps.