### Help with algorithm please!! I need a cross reference

Give an algorithm for finding the penultimate node in a singly linked list where the last element is indicated by a
null next pointer.

(Describe, in pseudo- code, how to insert an element at the beginning of a singly linked list, assuming that the list
does not have a sentinel header node, and instead uses a pointer variable head to point to the first node in the list.

* My idea of doing this is in psuedo code* I am just thinking of create a function and make a template for a linked list. Can someone help me answer these please? Thanks!
Well typical knowledge of a linked list includes the following:
1) A list consists of several nodes, all linked together
2) Each node consists of information, it's value and a pointer to the next one.

You're given this information:
1) Find the penultimate node (not sure what that is, but I believe that's the first node)
2) The list doesn't contain a "header" node, but does contain a pointer that points to the first node

1) Pointer points to first node
2) You need to insert a new node in the first one (what should it then point to?
3) The list pointer now needs to point to the new first node
4) You need to traverse the list until you can find a node where there isn't one after it (each node points to the next)

I hope this helps you understand without actually giving you the answer.
Penultimate

- create two pointer that points to first node. e.g ptr1, ptr2
- ptr1= ptr1->next;
while(ptr1)
{
if(ptr1->next == NULL) // traverse till last node
break;

ptr1 = ptr1->next;
ptr2 = ptr2->next; // by this your ptr2 will always precedes ptr1.
}

For Insert

- create one new node.. e.g newNode
- make that newNode->next = firstNode
- make head pointer to point newNode..
Last edited on
penultimate means second to last, i.e the one before the end.

I would use two iterators, one a step behind the other, and iterate through until the one ahead hits NULL, then the one before is at the penultimate, although it doesn't sound much like an algorithm.
Topic archived. No new replies allowed.