Author |
Topic: Reverse a linked list with a random node. (Read 3849 times) |
|
Ved
Junior Member
Gender: 
Posts: 53
|
 |
Reverse a linked list with a random node.
« on: Dec 9th, 2011, 11:02pm » |
 Quote  Modify
|
Consider a Linked List, in addition to having a 'next' pointer also has a 'random' pointer. The 'random' pointer points to some random other Node on the linked list. It may also point to NULL. To simplify things, no two 'random' pointers will point to the same node, but more than 1 Node's random pointer can point to NULL.
Now we are required to reverse the direction of all the pointers (both the 'next' and 'random') of the Linked list. The constraint is the solution MUST be O(1) space complexity (A constant number of new nodes can be created but not proportional to the length of the list)
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Reverse a linked list with a random node.
« Reply #1 on: Dec 12th, 2011, 1:15am » |
Quote Modify
|
If we just don't care about performance, you can define the functions:
- index(n) = position of n in the list.
- r_prev(n) = p such that p->random = n (or null)
- r_next(n) = n.random
- r_head(n) = result of repeating { n = r_prev(n) } while r_prev(n) is not null.
- r_tail(n) = result of repeating { n = r_next(n) } while r_next(n) is not null.
With all this, scan the list:
for each node n {
if( r_prev(n)==null ){
t = r_tail(n)
if( index(t)<index(n) ){
reverse the random list starting at n
}
if( r_next(n)==null ){
h = r_head(n)
if( index(h)<index(n) ){
reverse the random list starting at h
i.e reverse the list as if random were the "next" pointer.
}
}
then finish by reversing the whole list (reversing its "next" pointers).
It is something like O(n^3).
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Reverse a linked list with a random node.
« Reply #2 on: Dec 21st, 2011, 8:12am » |
Quote Modify
|
If we do not care about space, one solution can be this:
for every node n, insert a node n' between n and n.next , lets call n' as copy of n.
now do this for all the original nodes
n.random.next.random = n.next;
(what we are doing here is making the random field of newly added nodes to point exactly in opposite direction of the original nodes.
if A.random was B initially, the B'.random will be A' after this operation.)
Now separate the newly added nodes from the original list and make a new list of newly added nodes, which is reverse of the original list.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Reverse a linked list with a random node.
« Reply #3 on: Jan 10th, 2012, 9:42am » |
Quote Modify
|
I was just thinking, do we really need to take such complex solutions to this problem?
lets say A.random = B, B.random = C, C.random = D (where A, B, C, D do not necessarily occur in this order in the list)
Now if i have to reverse their random pointers, i have to keep track of the node which was pointed by the random pointer of the node i am going to change. So if i make B.random = A, i have to remember that B was pointing to C and in the next step, C's random should point to B. While changing C.random = B, i have to keep track of D, which was pointed by C.
Like this we can reverse the whole list. Does anybody see any problem with this solution?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reverse a linked list with a random node.
« Reply #4 on: Jan 10th, 2012, 10:42am » |
Quote Modify
|
What if all random pointers point to D?
In general, if you have a lot of short linked lists with the random pointers, you have to keep track of all those you've reversed in some way.
|
| « Last Edit: Jan 10th, 2012, 10:43am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Reverse a linked list with a random node.
« Reply #5 on: Jan 11th, 2012, 2:28am » |
Quote Modify
|
on Jan 10th, 2012, 10:42am, towr wrote:What if all random pointers point to D?
In general, if you have a lot of short linked lists with the random pointers, you have to keep track of all those you've reversed in some way. |
|
Its specified in the problem that no two random pointers will point to the same node..(otherwise to which node that node's random pointer will point after reversal ??)
But yes, NULL can cause problem here. So there will be small lists formed by ramdom pointer ending with NULL
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
fizyka
Junior Member
Physics&Informa tics <3
Gender:
Posts: 54
|
|
Re: Reverse a linked list with a random node.
« Reply #6 on: Jan 11th, 2012, 8:45am » |
Quote Modify
|
I had something simillar on my last laboratory from practise programming... I thought that it's imposibble to implement, because I really hate lists!! But it's second implementation looks good thx for that.
|
|
IP Logged |
fizyka , karta wzorów fizyka , książki z fizyki
|
|
|
krishnav
Newbie
Posts: 12
|
|
Re: Reverse a linked list with a random node.
« Reply #7 on: Jan 12th, 2012, 8:49am » |
Quote Modify
|
on Jan 10th, 2012, 9:42am, birbal wrote:I was just thinking, do we really need to take such complex solutions to this problem?
lets say A.random = B, B.random = C, C.random = D (where A, B, C, D do not necessarily occur in this order in the list)
Now if i have to reverse their random pointers, i have to keep track of the node which was pointed by the random pointer of the node i am going to change. So if i make B.random = A, i have to remember that B was pointing to C and in the next step, C's random should point to B. While changing C.random = B, i have to keep track of D, which was pointed by C.
Like this we can reverse the whole list. Does anybody see any problem with this solution?
|
|
what I understood from the problem description is that there could be several lists that can occur from the random pointers; what you laid out here won't work if there is more than one list with the random pointers
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print