C Puzzles
yet another place for C puzzlesWednesday, May 19, 2010
delete a node from circular singlely linked list with O(1)
You are given a circular single linked list of sufficiently many number of
nodes(say more than 1 crore). You need to delete a node say P and you are
given a pointer to P in the circular single list.
Suggest the most efficient methodology of deleting the node P from the
circular single linked list without rounding about the circular single
linked list.
Answer:
We have a list looking like: ... -> Node(i-1) -> Node(i) -> Node(i+1) -> ... and we need to delete Node(i).
- Copy data (not pointer, the data itself) from Node(i+1) to Node(i), the list will look like: ... -> Node(i-1) -> Node(i+1) -> Node(i+1) -> ...
- delete the second Node(i+1), it doesn't require pointer to the previous node.
Comments:
<< Home
copy the conetent of next node into the given node and delete the next node. say 100, 200, 300 are address locations of the three nodes in circular list. and now you are given 100. now copy content at 200 to 100, and make node in 100 point to 300 and now delete node at 200.
# posted by 
: 2:26 AM, May 21, 2010
: 2:26 AM, May 21, 2010
Yes. Psuedocode below:
DeleteNode(Node* pDelete)
{
Node *pNext;
pNext = pDelete->Next;
*pDelete = *pNext; // This should copy data as well as Next pointer from pNext into pDelete.
delete(pNext);
}
Post a Comment
DeleteNode(Node* pDelete)
{
Node *pNext;
pNext = pDelete->Next;
*pDelete = *pNext; // This should copy data as well as Next pointer from pNext into pDelete.
delete(pNext);
}
# posted by : 10:45 PM, August 13, 2010
: 10:45 PM, August 13, 2010Subscribe to Post Comments [Atom]
<< Home
Archives
July 2005 August 2005 October 2005 December 2005 March 2006 June 2006 July 2006 December 2006 February 2007 June 2007 March 2010 May 2010
Subscribe to Posts [Atom]