Reply to thread

Message

[QUOTE="CBFalconer, post: 1689694"]
I maintained earlier that use of list reversal would simplify
matters.  At any rate, just for sport I implemented both that and
the trailing pointer method below.  The code has been compiled and
run, and seems correct apart from a one-off error in the trailing
pointer method.  I am leaving that error in here, because I think
its existance is instructive. Note that the initialization
displays the list with the head last.

-------------- code begins here ---------------
#include <stdio.h>
#include <stdlib.h>

/* THERE ARE ERRORS HERE - possibly instructive */

#define POSN 5

struct node {
   struct node *next;
   int          val;
};

/* ----------------- */

/* make a list */
static struct node *initialize(void)
{
   struct node  n, *p;
   int          i;

n.next = NULL;
   for (i = 0; i < POSN + 2; i++) {
      p = n.next;
      if (!(n.next = malloc(sizeof *(n.next))))
         exit(EXIT_FAILURE);
      else {
         n.next->val = rand();
         n.next->next = p;
         printf("%d ", n.next->val);
      }
   }
   putchar('\n');
   return n.next;
}

/* ----------------- */

/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked  list.    Reentrant (pure) code */
static struct node *revlist(struct node *root)
{
   struct node *curr, *nxt;

if (root) {               /* non-empty list */
      curr = root->next;
      root->next = NULL;     /* terminate new list */
      while (curr) {
         nxt = curr->next;   /* save for walk */
         curr->next = root;  /* relink */
         root = curr;        /* save for next relink */
         curr = nxt;         /* walk onward */
      }
   }
/* else empty list is its own reverse; */
   return root;
} /* revlist */

/* ----------------- */

static void tryreversal(struct node *root)
{
   struct node *p;
   int    i;

root = revlist(root);
   p = root;
   for (i = 0; i < POSN; i++) p = p->next;
   printf("%dth from end via reversal is %d\n", POSN, p->val);

/* This only if original list must be unharmed */
   root = revlist(root);
} /* tryreversal */

/* ----------------- */

static void trytrailingptrs(struct node *root)
{
   struct node *last, *trail;
   int          i;

trail = last = root;
   for (i = 0; i < POSN; i++) last = last->next;
   while (last) {
      last = last->next;
      trail = trail->next;
   }
   printf("%dth from end via trailer is %d\n", POSN, trail->val);
} /* trytrailingptrs */

/* ----------------- */

int main(void)
{
   struct node *root;

root = initialize();

trytrailingptrs(root);
   tryreversal(root);
   return 0;
}
[/QUOTE]

Verification