Program to swap first and last node of a list -> Adobe Question

public void swapFirstLast(){
Node current = head;
Node previous = null;
while(current.next != null){
previous = current;
current = current.next;
}
Node temp = head;

current.next = temp.next;
previous.next = temp;
temp.next = null;
head = current;

}

Linked List questions(Good one)

Q2 : You are give a node in a linked list and you need to delete it from the list..

Sol: the problem is that we have to delete the node.. but dont know the node before that ... so what we can do is copy the content of the node next to it in the current node .. and simply delete the next node...instead of transfering all teh content iteratively till the end.

Reference :http://www.tekpool.com/node/107

Q3: How to find common node in intersecting linked lists
Sol : There is no need to reverse the link lists. All we need to do is to first calculate len=len1-len2 (len1>len2, as discussed above). Point p1 and p2 to list1 (the longer one) and list2 respectively. Then step only p1 for "len" no. of nodes. After this we are guaranteed that p1 and p2 are equidistant from the common node. So now start stepping p1 and p2 simultaneously until p1==p2. This will the common node. This is a simple O(n) solution.

Linked List Interview questions

Question : how does one find a loop in a singly linked list in O(n) time using constant memory? you cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n.)

Sol: One way to detect a loop is to iterate over the list with 2 pointers at the same time where one is iterating at double speed. If the 2 pointers are ever equal after they iterate once and before they both reach an end, there's a loop.

However , this may not be the best solution if the loop is very long as we ll have to iterate with in the loop many times. So, a better approach would be to associate a variable with each node and change or set its value once the node is encountered. So If we encounter a node whose variable value has already been set, that means we ve already traversed that node and thus be sure that loop exists.