Reversing a Linked-list

♠ Posted by GeekyFry in ,,,,, at 7:05 AM
 How do you reverse a singly linked list? How do you reverse a doubly linked list? Write a C program to do the same.

Reversing a Singly linked list:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct node {
  int data;
  struct node *link;
};
void reverse() {
   struct node *p = first, *q = NULL,  *r;
   while (p != NULL)  {
      r = q;
      q = p;
      p = p->link;
      q->link = r;
   }
   q = first;
}
Reversing a doubly linked list:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* a node of the doubly linked list */
struct node
{
  int data;
  struct node *next;
  struct node *prev;
};
 
/* Function to reverse a Doubly Linked List */
void reverse(struct node **head_ref)
{
  struct node *temp = NULL;
  struct node *current = *head_ref;
 
/* swap next and prev for all nodes of doubly linked list */
  while (current != NULL)
  {
    temp = current->prev;
    current->prev = current->next;
    current->next = temp;
    current = current->prev;
  }
 
/* Before changing head, check for the cases like empty list and list with only one node */
  if(temp != NULL )
  *head_ref = temp->prev;
}

0 comments:

Post a Comment