A Challenging One : How to convert a singly linked list into a staggered linked list using C languag-CodePudding

A Challenging One: How to convert a singly linked list into a staggered linked list using C language? By Modifying the order of a linked list in the following pattern, adding the current node to the result list after every step:

Start at the head

Take two steps forward

Take one step back

Take three steps forward

Go to step 3 unless outside end of list

Add unvisited element at end of list to result, if any

Example 1 : Odd no. of elements

Input:

0->1->2->3->4->5->6->7->8->NULL

Output:

0->2->1->4->3->6->5->8->7->NULL

Example 2: Even no. of elements

Input:

0->1->2->3->4->5->6->7->NULL

Output:

0->2->1->4->3->6->5->7->NULL

For one or two elements, return as is.

For 3 elements:

Input:

0->1->2

Output:

0->2->1->NULL

Here's what I tried but not running successfully on all input cases:

#include <stdio.h>

struct Node {
    const int val;
    struct Node *next;
};

void stagger(struct Node *head) {
    struct Node *curr, *slow, *fast='\0';
    curr = head;

    if (curr == '\0') {
        printf("NULL");
        return;
    }

    if (curr->next == '\0' || curr->next->next == '\0') {
        while (curr) {
            printf("%d->",curr->val);
            curr = curr->next;
        }
    } else {
        while (fast) {
            printf("%d->",curr->val); //0-1
            fast = slow->next->next;
            slow = curr->next;
            printf("%d->",fast->val); //2-1
            printf("%d->",slow->val); //1-1
            curr = slow->next->next;
            printf("%d->",curr->val);
        }
    }

    printf("NULL");
}

CodePudding user response：

The algorithm you described can be thought of as swapping every two consecutive nodes after the zeroth.

This task can be made very simple:

// n0 must not be NULL
void stagger(struct Node *n0) {
  struct Node *n1 = n0->next;
  if (!n1) return;
  struct Node *n2 = n1->next;
  if (n2) {
    /*
      at this time, n0->n1->n2->n3...
      we want n0->n2->n1->n3...
      n0, n1, and n2 are all valid pointers to Nodes. n3 may be NULL
    */
    struct Node *n3 = n2->next;
    n0->next = n2;
    n1->next = n3;
    n2->next = n1;
    // n1 will be n0 in the next call to stagger, with n1->n3... now n0->n1...
    stagger(n1);
  }
}

If recursion is not your thing, the same can be achieved with a while-loop.

CodePudding user response：

Thanks to nathaniel

That was of much help in rearranging the pointers, and here the final version I reached (just made n0 to head and added printing) that works as expected in the challenge

#include <stdio.h>

struct Node {
    int val;
    struct Node *next;
};
 void stagger(struct Node *head) {

  if(!head) // handling empty list
  {
    printf("NULL");
    return;
  }
   struct Node *n1 = head->next;

  if(!head->next || !head->next->next ) // handling 1 or 2 elements
  {
    while(head)
    {
      printf("%d->",head->val);
      head = head->next;
    }
    printf("NULL");
    return;
  }
   
  struct Node *n2 = n1->next;
  if(n2)
  {
    printf("%d->",head->val);
    printf("%d->",n2->val);
    struct Node *n3 = n2->next;
    head->next = n2;
    n1->next = n3;
    n2->next = n1;
    stagger(n1);

  }
}

I hope this might help, Actually This code modifies the original list and Here I ask for one more contribution to save the newly arranged elements into a new list without modifying the old one, It's very simple :)