Bloomberg LP Interview Question
Financial Software DevelopersWhat kind of Singly linked list are you referring to? Please clarify ...
1. Basic singly linkedlist
2. Double "ended" sinlgly linked list (pointer to the head and the tail elements of the list
3. Circular singly linkedlist
4. Singly linked list w/ a sentinel
static void findMiddleElement(LinkedListNode head) {
// LinkedListNode head = new LinkedListNode(1);
// head.appendToTail(2);
// head.appendToTail(3);
// head.appendToTail(4);
// head.appendToTail(5);
// head.appendToTail(6);
// head.appendToTail(7);
// head.appendToTail(8);
// head.appendToTail(9);
// head.appendToTail(10);
// head.appendToTail(11);
LinkedListNode current = head;
LinkedListNode middle = head;
while (current.next != null) {
current = current.next;
if (current.next != null) {
current = current.next;
middle = middle.next;
}
}
System.out.println("Middle Element :" + middle.value);
}
public class LinkedListNode {
public LinkedListNode next;
public LinkedListNode previous;
public int value;
public LinkedListNode(int value) {
this.value = value;
}
public void appendToTail(int value) {
LinkedListNode end = new LinkedListNode(value);
LinkedListNode temp = this;
while (temp.next != null) {
temp = temp.next;
}
temp.next = end;
}}
Here is the code for java programmers
static void findMiddleElement(LinkedListNode head) {
// LinkedListNode head = new LinkedListNode(1);
// head.appendToTail(2);
// head.appendToTail(3);
// head.appendToTail(4);
// head.appendToTail(5);
// head.appendToTail(6);
// head.appendToTail(7);
// head.appendToTail(8);
// head.appendToTail(9);
// head.appendToTail(10);
// head.appendToTail(11);
LinkedListNode current = head;
LinkedListNode middle = head;
while (current.next != null) {
current = current.next;
if (current.next != null) {
current = current.next;
middle = middle.next;
}
}
System.out.println("Middle Element :" + middle.value);
}
public class LinkedListNode {
public LinkedListNode next;
public LinkedListNode previous;
public int value;
public LinkedListNode(int value) {
this.value = value;
}
public void appendToTail(int value) {
LinkedListNode end = new LinkedListNode(value);
LinkedListNode temp = this;
while (temp.next != null) {
temp = temp.next;
}
temp.next = end;
}}
using two pointers
- xiaogold March 25, 2010