What is wrong with my logic to rotate a doubly linked list?

Question

Given a doubly-linked list, rotate the linked list counter-clockwise by P nodes. Here P is a given positive integer and is smaller than the count of nodes (N) in a linked list. The first line contains the number of test cases. Each test case consists of two lines, one specifying N and P, the other the list of values.

Example: Input:

1
6 2
1 2 3 4 5 6

Output:

3 4 5 6 1 2

I have written a function to do the rotation as given. I keep getting a runtime error. You can refer to https://practice.geeksforgeeks.org/problems/rotate-doubly-linked-list-by-p-nodes/1/ for the official problem definition.

struct node *rotate(struct node *head){ 
    int num, count=1;
    struct node *current, *nnode;
    current=head;
    printf("\nEnter the number across which you wanna rotate: ");
    scanf("%d", &num);
    if(num==0){
        return;
    }
    while(count<num && current!=NULL){
        current=current->next;
        count++;
    } 
    if(current==NULL){
        return;
    }
    nnode=current;
    while(current->next!=NULL){
        current=current->next;
    }
    current->next=head;
    head->prev=current;
    head=nnode->next;
    head->prev=NULL;
    nnode->next=NULL;
    return head;
}

Answer 1

Unless you are stuck with a linear list, I would suggest that you use a circular one, i.e., one where the next of the last link points to the first link. You can work with them just as you would any other "linear" list; you just want to check if you return to where you start when you loop through them, rather than test if you reach NULL. You get a special case when you create links, and sometimes when you insert them if you have an empty list, but nothing worse than you get otherwise. (If you don't need to move the head around, as you do with rotation, then you handle that with a dummy node, and you get rid of a lot of special cases that you have with non-circular lists).

Some simple code for a circular list (without a dummy link, so a list that can be NULL) can look like this:

struct link {
  int value;
  struct link *prev;
  struct link *next;
};

static inline
void connect_neighbours(struct link *x)
{
  x->next->prev = x;
  x->prev->next = x;
}
static inline
void link_after(struct link *x, struct link *y)
{
  y->prev = x;
  y->next = x->next;
  connect_neighbours(y);
}
#define link_before(x, y) \
  link_after((x)->prev, y)

struct link *new_link(int val,
                      struct link *prev,
                      struct link *next)
{
  struct link *link = malloc(sizeof *link);
  if (!link) return 0;

  link->value = val;
  if (prev == 0 || next == 0) {
    // make a link circular if we don't have prev/next
    link->next = link->prev = link;
  } else {
    // otherwise, just set the links
    link->prev = prev;
    link->next = next;
  }
  return link;
}

That is code for creating links, linking prev and next to the node itself if we don't provide pointers to links, and for putting a new link before or after a link. The link_after() and link_before() operations will, of course, fail if you give them NULL pointers, so you cannot use them until you have a list with at least one link in it.

To run through a list, for example, to print it, you can write code such as this:

void print_list(struct link *head)
{
  if (!head) {
    printf("[]\n");
    return;
  }
  printf("[ ");
  printf("%d ", head->value);
  for (struct link *link = head->next;
       link != head;
       link = link->next) {
    printf("%d ", link->value);
  }
  printf("]\n");
}

The for-condition, where we check if we are back to the head, is how we recognise that we are done. The special case for an empty list, and handling the first link outside the loop, is not necessary if you have a dummy link either, but for the rotation operation, it is easier if we not have a dummy. If we don't, then rotating is as simple as following next or prev pointers the right number of times:

struct link *rotate(struct link *x, int rot)
{
  if (rot > 0) {
    for (; rot; rot--) x = x->next;
  } else {
    for (; rot; rot++) x = x->prev;
  }
  return x;
}

With the code above, you can create and rotate a list like this:

int main(void)
{
  struct link *x = 0;
  print_list(x);

  // not checking allocation errors here!
  x = new_link(1, 0, 0);
  for (int i = 2; i <= 5; i++)
    link_before(x, new_link(i, 0, 0));
  print_list(x);

  print_list(rotate(x, 2));
  print_list(rotate(x, -2));

  return 0;
}