Pergunta de entrevista da empresa Amazon

Find the last element of a linked list.

Respostas da entrevista

Sigiloso

28 de dez. de 2010

public *Node LastElement(Node *Head) { while(Head->next != null) { Head = Head->next; } return Head; }

1

Sigiloso

21 de jan. de 2011

Did they really ask you this question? Although Praveen's answer is correct, It seems that his answer would also be very time-consuming. Is there another way to find the last element on a linked list - assuming that it's singularly linked?

1

Sigiloso

20 de fev. de 2011

Because the parameters are always passed by value. Even if you modify the input parameters, the original variable remains unchanged.

1

Sigiloso

21 de fev. de 2011

I am talking about the case where you don't specifically pass the params as references in C++. In C, my statement holds.

1

Sigiloso

3 de out. de 2011

All the answers are partially correct. Anonymous: The function accepts a pointer not a reference to the pointer (pass by value). Hence if the pointer 'Head' is modified in the function, it doesn't affect the actualy pointer that was passed into the function. However, what's missing in Praveen's solution is the boundary condition of whether the Head node is NULL. If it is, then the starting statement of the while loop is going to access a NULL pointer. The correct solution should be something like: Node* GetLastNode(Node* head) { // Loops through till the end of the node for(; head != NULL && head->next; head = head->next); // Return the last node (This could be NULL if head was NULL). return head; }

Sigiloso

21 de jan. de 2011

Did they really ask you this question? Although Praveen's answer is correct, It seems that his answer would also be very time-consuming. Is there another way to find the last element on a linked list - assuming that it's singularly linked?

Sigiloso

20 de fev. de 2011

praveen's answer is correct but not good enough, you would not want to modify the pointer you got it might be your only ptr to the head of the list. public *Node LastElement(Node *Head) { Node *iter = Head; while(iter->next != null) { iter = iter->next; } return iter; } would be more correct.