[Interview] 4. Reversing a Singly Linked List

Refer to the classic blog post: Linked List Reversal

Given the head pointer Head of a singly linked list, the linked list can be reversed. One method uses direct pointer assignment, and another leverages the LIFO (Last-In, First-Out) property of a stack.

#include<iostream>#include<stack>using namespace std; struct node{    int i;    node* next;}; void reverse1(node** head){    node* p1;    node* p2;    p1=*head;    p2=p1->next;    (*head)->next=NULL;    while(p2)    ...{        p1=p2->next;        p2->next=*head;        *head=p2;        p2=p1;    } }void reverse2(node** head){    stack<node*> S;    node* temp=*head;    while(temp)    {        S.push(temp);        temp=temp->next;    }    *head=S.top();    S.pop();    temp=*head;    while(!S.empty())    {        temp->next=S.top();        S.pop();        temp=temp->next;        temp->next=NULL;    }} int main(){     node* head=new node;    head->i=0;    head->next=NULL;    node* temp=head;    int i;    for(i=1;i<10;++i)    {        temp->next=new node;        temp=temp->next;        temp->i=i;        temp->next=NULL;    }     temp=head;    while(temp)    {        cout<<temp->i<<endl;        temp=temp->next;    }     reverse1(&head);    temp=head;    while(temp)    {        cout<<temp->i<<endl;        temp=temp->next;    }     reverse2(&head);    temp=head;    while(temp)    {        cout<<temp->i<<endl;        temp=temp->next;    }      return 0;}