Yahoo! : Best Linked List Questions

Wednesday, 1 August 2012 | Unknown at 21:51 |

How to Approach:
Linked list questions are extremely common. These can range from simple (delete a node in a linked list) to much more challenging. Either way, we advise you to be extremely comfortable
with the easiest questions. Being able to easily manipulate a linked list in the simplest ways will make the tougher linked list questions much less tricky. With that said, we present some “must know” code about linked list manipulation. You should be able to easily write this code yourself prior to your interview.
Creating a Linked List:
NOTE: When you’re discussing a linked list in an interview, make sure to understand
whether it is a single linked list or a doubly linked list.
1 class Node {
2 Node next = null;
3 int data;
4 public Node(int d) { data = d; }
5 void appendToTail(int d) {
6 Node end = new Node(d);
7 Node n = this;
8 while (n.next != null) { n = n.next; }
9 n.next = end;
10 }
11 }
Deleting a Node from a Singly Linked List
1 Node deleteNode(Node head, int d) {
2 Node n = head;
3 if (n.data == d) {
4 return head.next; /* moved head */
5 }
6 while (n.next != null) {
7 if (n.next.data == d) {
8 n.next = n.next.next;
9 return head; /* head didn’t change */
10 }
11 n = n.next;
12 }
13 }

2.1 Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?
_
_______________________________________________________________
2.2 Implement an algorithm to find the nth to last element of a singly linked list.
_
_______________________________________________________________
2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e
_
________________________________________________________________
2.4 You have two numbers represented by a linked list, where each node contains a single
digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8
_
______________________________________________________________
2.5 Given a circular linked list, implement an algorithm which returns node at the beginning
of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C
_
________________________________________________________________