Today's Question:  What's your opinion about Alibaba mooncake incident?        GIVE A SHOUT

Technical Article => Programming =>  Algorithm

Algorithm : Reverse singly linked list

  Pi Ke      2015-10-31 11:38:35      692    0    0

Questions about singly linked list are the lovers of interviewers during interviews given the characteristic that singly linked list is one-directional list and it's difficult to get the previous node of one node without some buffering tricks. 

In this post, we will demonstrate one of the most frequently asked question about singly linked list -- Reversing the singly list.

Given the first node of a singly linked list, reverse the singly linked list. For example :

A->B->C->D

After reverse, it becomes:

D->C->B->A

The general idea here is to changing the next node of one to its previous node to realize reverse. The most difficult part to resolve this problem is able to find the next node of the one node after changing its next node to its previous node. To achieve this, a buffering to the node's next node is needed before changing its next node to its previous node.

Below is the sample code to this issue.

#include <stdio.h>

struct Node {
	struct Node* next;
	char value;
};

// Print the singlely linked list
void printList(struct Node* head){
	while (head != 0){
		printf("%c->", head->value);
		head = head->next;
	}
	printf("null\n");
}

// Reverse the singly linked list
struct Node* reverseList(struct Node* node){
	struct Node* currentNode = 0;

	while (node){
		struct Node* next = node->next;
		node->next = currentNode;
		currentNode = node;
		node = next;
	}

	return currentNode;
}

int main(){
	struct Node* a = malloc(sizeof(struct Node));
	struct Node* b = malloc(sizeof(struct Node));
	struct Node* c = malloc(sizeof(struct Node));
	struct Node* d = malloc(sizeof(struct Node));

	a->value = 'A';
	b->value = 'B';
	c->value = 'C';
	d->value = 'D';

	a->next = b;
	b->next = c;
	c->next = d;
	d->next = 0;

	// print the original list
	printList(a);

	// Reverse list
	struct Node* head = reverseList(a);

	// print the new list
	printList(head);

	free(a);
	free(b);
	free(c);
	free(d);
}

The output of this program is :

A->B->C->D->null
D->C->B->A->null

You may also be interested to Algorithm : Delete middle node from singly linked list.

C ALGORITHM INTERVIEW

  SAVE AS PDF   MARK AS READ   MARK AS IMPORTANT

Share on Facebook  Share on Twitter  Share on Google+  Share on Weibo  Share on Reddit  Share on Digg  Share on Tumblr    Delicious

  RELATED


  0 COMMENT


No comment for this article.


  WRITE ARTICLE

Adapter design pattern explained

By sonic0002