If the head of a linked list is pointing to kth element, then how will you get the elements before kth element?

Question

I search this question over web and get the ans that it can be implemented using XOR linked list or the linked list in the question has to be doubly linked list.

But I'm thinking the question is not complete in itself because for implementing XOR linked list function, the next pointer of the node must be in the suitable form i.e (next pointer) xor (previous pointer). But nothing is given. Provide me some good solution.

Answer 1

It is not possible to navigate from any random (kth) element to its neighbour. You need the predecessor to navigate to the successor. You need the successor to navigate to the predecessor. In order to fulfill this requirement you can store a pointer to the kth and (k+1)th element in the header.

If you can´t store the (k+1)th element, the only way to find the predecessor is to loop through the list from the beginning (or end) until you find the kth element - then you can go backwards.

Hope this helps. I never worked with xor-linked lists. But this is what I found out here.

Answer 2

If the head of a linked list is pointing to kth element

then, where is the first element?

If it is a single linked list, and the given "head" is not actually the first element, but somewhere in the middle, then without the real head, I think elements before it can't be reached.

May I ask is it a leetcode problem? If yes, it is reasonable. Problems are often not clearly described in the site.

Answer 3

You cannot get the elements before the position k unless the list is a doubly linked list. If each node points to its following node, and thats the only connection it carries, how is it supposed to access the previous node? Think of it like an iteration: you cannot go back once you call upon the next value.

If it is necessary to access the values before k, you may either 1) save the elements when you come across them (probably not a good idea) or 2) should consider using another data structure, depending on the implementation.

Answer 4

Here it is written that head is pointing to some kth element. we know in XOR linked list the pointer of head contains xor of NULL and address of second element,so in this case xor of NULL and second element is same as the address of some k th element;

i will save the pointer of head in some pointer p,and keep traversing the XOR linked list till the address of p matches with the current node.

node* p = head->ptr;
node* prev = NULL;
node* curr = head;
node* next = NULL;

while(curr!=p && p)
{
   next = xor(prev,curr->ptr);
   print(curr->data);
   prev = curr;
   curr = next;
}

Answer 5

We can use XOR linked list (memory efficient linked list) for this.

XOR linked list is a linked list of which next pointer contains the address as XOR of Previous and Next node address. So, that whenever we need to access next element just XOR it with previous and vice versa for previous element.

Answer 6

XOR linked list or Memory efficient linked list can be used.

let's say you have LL: 1->2->***3***->4 and your head is pointing on the 3rd node.

Using the XOR ll we know that :

1 -> NULL ^ 2
2-> 1 ^ 3
3-> 2 ^ 4
4-> 3^ NULL

So here in order to find the address of 2 and 1, we use the equation 3 -> 2 ^ 4 we know the address of 3 (as it is head) and the address of 4( head. next) so if we XOR 4 on both the side we get:

3^4 -> 2 ^ 4 ^ 4 (using the XOR property : 0 ^ 0 -> 0)

we get : 3 ^ 4 -> 2

this means that the prev element is the XOR of the head and the next of the head element.

So, this is how XOR can be used to find the prev element when the kth element is given as head.