• C

# Deleting from a Linked List.

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.

###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
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
Commented:
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.
DBACommented:

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
Commented:
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.
Commented:
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.
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.

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; }

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author Commented:
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?
Commented:
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
DBACommented:

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
Commented:
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).

Commented:
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..... )

DBACommented:

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
Commented:
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.

DBACommented:

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
Commented:
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.
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.