Solved

Deleting from a Linked List.

Posted on 2003-11-07
14
389 Views
Last Modified: 2011-09-20
Hi,
I need to know if this is possible.

Problem:
Delete the last 'K' Nodes of a linked list.
Restrictions:
1.In only one parse.
2.You have only the start pointer.
3.The number of nodes in the Linked list is not known.
Assumptions:
1.'K' is greater than the number of nodes in the List.

All the restrictions and assumptions apply together. I need the approach to the solution.'C' Code will be appreciated.

Thanks to anyone who answers.
0
Comment
Question by:mdn3din
14 Comments
 
LVL 9

Expert Comment

by:tinchos
ID: 9703486
My fast answer to that question is
No, it is not possible.

Explanation.........

Assumptions:
1.'K' is greater than the number of nodes in the List.

Then how can you delete more nodes than the ones existing?

If that assumption is not valid.......... then

If you want to delete the last k nodes and you just have the starting node, and you don't know the number of nodes, then you must go to the end in order to know which nodes you have to delete.......

So, it's impossible to do it in one parse.

Hope this helps

Tincho
0
 
LVL 6

Expert Comment

by:MannSoft
ID: 9703547
If it is doubly linked, then once you find the end you can move in reverse.  Depending on whose definition you go by, that could be considered one parse.  And it is possible with a singly linked list too, but you would need some sort of a temporary array.  Conventional delete methods wouldn't work.
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9703651

Well, your one assumption is false.  K needs to be LESS than the total number of nodes in the list.

It is quite possible, though not very efficient.

Write a recursive function that scans to the end of the list.

When the last node is encountered, the function returns a 1.

When the value 1 is returned to the next instance, it is compared against K.  if (value < K) the child node is deleted.

The (now) current node adds 1 to the value returned by its child and returns this value to its parent.

This node checks the returned value against K.  if (value < K) the child node is deleted.


The last two steps repeat until K nodes are deleted or until the entire list is deleted.


Kent
0
 
LVL 11

Expert Comment

by:KurtVon
ID: 9704257
I think this was meant to be a trick question.  If K is larger than the number of nodes, it is easy to perform the requested action.

Delete all the nodes.
0
 
LVL 22

Accepted Solution

by:
grg99 earned 200 total points
ID: 9704560
If we assume you mean in one PASS, and K is LESS than the number of nodes, yes you can do it in one pass.

you need two pointers, let's call them p and q.
q is the leader, K nodes ahead of p.
We go down the list until q hits the end.
Then p catches up to q, freeing nodes as it goes.
There's an intentional off-by-one error in there (twice) to leave you something to do.


p = head;  q = head;
for( i = 1; i <= K; i++ ) if( q != NULL ) q = q->Next;    

while( q != NULL ) {
 p = p-> Next;  q = q->Next; }

while( p != NULL ) { q = p->Next; free( p ); p = q; }
0
 

Author Comment

by:mdn3din
ID: 9705359
Hi,

Yes the assumption that 'K' is greater than the number of nodes is false, it should be LESS!. A typing error,was in a hurry, sorry for the confusion!

Kent,
Do you mean this?

int delete(NODE *p)
{
            if(p->next)
            {
                         if(delete(p->next) <= k)
                         {
                                     free(p->next);
                                     p->next=NULL;
                          }
           }
           return(++count);
}

It works but how is it inefficient?
0
 
LVL 15

Expert Comment

by:efn
ID: 9705774
Kent's solution is inefficient and possibly impractical for large lists because it effectively makes a copy of the entire list structure on the function call stack.  If you have a list with thousands of nodes, that design will require thousands of recursive function calls.

grg99 gave you the elegant solution, requiring only two pointers.

--efn
0
Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

 
LVL 45

Expert Comment

by:Kdo
ID: 9711255

Sorry for the delay in getting back to you -- I've been away for a few days.

grg's solution is quite elegant (he does that a lot), but when you turn this in as a completed assignment, I'll bet that you get no point for originality.   The problem is straight out of comp-sci 101 and is intended to get you to think about recursion and how it works.  In the "real world" I'd use something similar to grg's due to its efficiency.  My solution is inefficient on a very large list.  There's too much stack manipulation, the stack can get large enough to cause unnecessary page faulting, and on systems with a stack size limit the program might not run at all.

But it is the solution that your instructor is looking for.  grg's is a quasi-violation of the rules by being 1+ passes -- it moves two pointers the length of the list (albeit in three loops that never overlap ranges giving a good argument to it being one pass).

Recursive code to do this is quite simple.

/*  p is the current node to evaluate  */
/*  K is the number of nodes to delete  */
DeleteChain (Note *p, int K)
{
  int DeleteCount;

/*  Move to the end of the chain  */

  if (p)
    DeleteCount = DeleteChain (p->next, K); /*  Move to the end of the chain  */
  else
    return (0);

/*  We've traversed the chain to the end.  Delete nodes as appropriate */

  if (DeleteCount < K)
    free (p);
  return (DeleteCount+1);
}

The value returned to the original call is the number of nodes in the original chain.


Kent
0
 
LVL 22

Expert Comment

by:grg99
ID: 9711692
There's no need for the recursive version to recur N times, K should be enough.. I'll try to code it up during "Midway", (the movie).

0
 
LVL 22

Expert Comment

by:grg99
ID: 9715143
Ach, such a lousy movie noone should have to sit thru.  To cal the acting wooden is to denigrate that underappreciated cellulose substance.  Good original film clips tho.

Now back to the pointer question, I *think* you could do it by recurring, say K+Q times, where for efficiency, K+Q should be like no less than N/20 or so.  Go down the list recursively, K+Q times, or until you hit the end.  If you hit the end, return back K times, freeing nodes as you go.  If you didnt hit the end, return the last pointer ALL the way back up the chain and repeat.   A tad clumsy, but it should do the trick.   Code is *roughly* like this:

int K = 10; int Q = 20;

typedef Node * NodePtr;

NodePtr Plunge( int Depth, NodePtr p )
{
    if( p == NULL ) /* hit end */ return(  NULL );
    else if( Depth < K ) { q = Plunge( --Depth, p->Next ); if(  q == NULL) { free( p ); return(NULL); }
else  /* may be returning deepest ptr */ if( K == Depth ) p = q; else return( Plunge( --Depth, p->Next ) );
else /* didnt hit end */  return(  p  );
}


Plunge( K + Q, Head );

----

Whew!

( BTW this explains why pure LISP has never caught on that well..... )


 
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9716703

Hi grg,

At your age I would have thought that you'd seen the movie enough times to have it memorized.  I enjoyed it the first 81 times through, but it has gotten a bit stale.  :)  (I've always preferred "Tora, Tora, Tora".)


Kent
0
 
LVL 22

Expert Comment

by:grg99
ID: 9717149
I've never seen the movie before.  I did *hear* it when it was originally in the theaters circa 1976, and you could hear the "SenseSurround" BOOMS! from adjacent theaters.

I didnt see much use of recursion in the movie, except where Teddy Roosevelt Junior was talking about his father's military experiences.
Oh, and Hal Holbrook's character's elevator didnt go all the way to the top, while he was on that carrier's elevator, which did go to the top, and return.

0
 
LVL 45

Expert Comment

by:Kdo
ID: 9717326

Holbrook was the movie's "saving grace".  Never bathed, didn't notice those around him that didn't, thought that having 10% was pretty cool, got giddy over being right over a potential disaster.  Typical systems analyst.

The rest of the movie was a stretch, though I agree that the use of historical clips was well done.  And the ending was OK, too -- standing on the bridge reflecting over what had happened.

But it's hardly worth the other 3 hours of film.


I'm trying to get a handle on Plunge().  It seems to be "mixing metaphores".  :)  What are the roles of Q and q?  And how does it work?

Kent
0
 
LVL 22

Expert Comment

by:grg99
ID: 9717450
Oh, I never said it *worked*.   Basic idea is to recur down a ways, if you don't hit the end, return how far you got so the next iteration can start from there.
if you do hit the end, delete K nodes on the way back up.  I was trying to watch the movie, write the code, pet the dog, explain to my son that Japanese and Americal admirals did not stand rigidly around an overlit map and argue about plans.  That and the *%$%^$*& pen wouldnt write more than three inches without skipping.  Doctor's offices have to start stocking better quality pens for us to borrow.  
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now