top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to get data of previous node that is (k-1) when head is pointing to k node?

+3 votes
660 views

Solve this problem using singly linked list data structure and given that you can't use doubly linked list.I tried to take inverse but it didn't help because head is pointing to k th node and I need to access k-1 th node according to problem.
Example : 5->2->4(head)->7->null
head points to 4 and output: 2

posted Sep 6, 2016 by Shivam Kumar Pandey

Looking for an answer?  Promote on:
Facebook Share Button Twitter Share Button LinkedIn Share Button
Hi Shivam, i have couple of question regarding inputs.

1> Can we use single circular linked list ?
2> What will the input for the function
           i> Head pointer only which is pointing to any valid node in list.
          ii> Head pointer and kth element number also
No,
1. only singly LL as I mentioned in the description and
2. inputs
 i & ii. as in case of singly LL, there is only one head pointer so here we will use only one head pointer which will point to k th node only.
No as per point 2, i am asking the value of k is given ? Element number not value ?
no doubt it will be given ..
input set : numberOfElements= 5
list = 3->5->7->9->1->null and
head points to = 7
output= 5
We can use XOR linked list which is used in double linked list, but to solve i need address of next node present after head.

Source : https://en.wikipedia.org/wiki/XOR_linked_list
As in case of xor linked list
...       A           B             C                D          E  ...
Ptr   0⊕B <–>A⊕C<->B⊕D  <->  C⊕E  <->D⊕0

Suppose head is pointing to B suppose,
To get address of A = (B->ptr) ⊕ C =( A⊕C ) ⊕ C = A

So A of value will be the answer. But i dont have address of C which is next to head.
thanks I got your idea and again we can't use doubly linked list because if we use it,there is no need of xor
I am searching for a solution which uses singly linked list + xor
The comment i have given is not or doubly linked list, i am telling to apply the principle in single linked list only.Only ptr = Addrs(Prev) XOR Addrs(Next)
Ok and  from your wikipedia link,I got this http://www.linuxjournal.com/article/6828 article where I got  a memory efficient method explained by Prokash Sinha for my problem. Thank you

Similar Questions
+2 votes

Two BSTs(of size m and n) are given which have all values distinct but they have one value in common which is called their intersection point, output that point in minimum time complexity ?

+2 votes

You have a binary tree which consists of 0 or 1 in the way, that each node value is a LOGICAL AND between its children:

      0
   /    \
  0      1
 / \    / \
0   1  1   1

You need to write a code, which will invert given LEAF and put tree in a correct state.

Note: Received by some user over whatsapp, sharing in exact form?

...