Reverse a singly-lined list without second access
Solution
Loop through singly-linked list
Cut off the previous reference
Add backward reference
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
typedef struct single_linked_node{
int data;
struct single_linked_node *next;
}Node;
Node *create_node(int data)
{
Node *p = NULL;
p = new Node;
if(p != NULL){
p->data = data;
p->next = NULL;
}
return p;
}
Node *append_node(Node **head, int data)
{
Node *node = create_node(data);
if(*head == NULL){
*head = node;
}
else{
Node *p = *head;
while(p->next){
p = p->next;
}
p->next = node;
node->next = NULL;
}
return *head;
}
int get_list_len(const Node* head)
{
int l = 0;
while(head != NULL){
head = head->next;
l++;
}
return l;
}
void print_list(const Node* head)
{
while(head != NULL){
cout << "Address: " << head << " Data: " << head->data << endl;
head = head->next;
}
}
Node* del_node(Node **head, int data)
{
Node *p;
if(*head == NULL){
return NULL;
}
p = *head;
while(p!= NULL &&p->data == data){
p = p->next;
delete *head;
*head = p;
}
while(p != NULL && p->next != NULL){
if(p->next->data == data){
Node *p1 = p->next;
p->next = p->next->next;
delete p1;
}
else{
p = p->next;
}
}
return *head;
}
Node* insert_node(Node **head, Node *node, int data)
{
Node *p = create_node(data);
if(node == *head){
p->next = *head;
*head = p;
}
else{
Node *p1 = *head;
while(p1->next != node){
p1 = p1->next;
}
Node *p2 = p1->next;
p1->next = p;
p->next = p2;
}
return *head;
}
Node* reverse_list(Node **head)
{
if(*head == NULL || (*head)->next == NULL){
return *head;
}
Node *p1 = *head;
Node *p2 = (*head)->next;
p1->next = NULL;
while(p2 != NULL && p2->next != NULL){
Node *p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
p2->next = p1;
*head = p2;
return *head;
}
int main(int argc, char* argv[])
{
int i;
Node *head = NULL;
srand((unsigned)time(NULL));
for(i = 0; i < 10; i++){
append_node(&head, i);
append_node(&head, 10);
}
print_list(head);
cout << "List lenght is: " << get_list_len(head) << endl;
reverse_list(&head);
print_list(head);
cout << "after deleting 10" << endl;
del_node(&head, 10);
print_list(head);
cout << "after deleting 9" << endl;
del_node(&head, 9);
print_list(head);
cout << "after deleting 5" << endl;
del_node(&head, 5);
print_list(head);
cout << "after deleting 0" << endl;
del_node(&head, 0);
print_list(head);
return 0;
}
Output