연결 리스트 뒤집기 (Reverse Linked List) ​

class Node
{
public:
 Node *next;
 int data;

 // item을 data에 넣고 다음노드를 next에 넣음
 Node(const int& item, Node* ptrnext = NULL);

 // p를 자신의 다음 자리에 끼워넣음
 void InsertAfter(Node *p);

 // next를 리스트에서 제외하고 제외된 포인터를 반환
 Node* DeleteAfter(void);
};

#include "Node.h"

Node::Node(const int& item, Node* ptrnext)
{
 data = item;
 next = ptrnext;
}

void Node::InsertAfter(Node *p)
{
 p->next = next;
 next = p;
}

Node* Node::DeleteAfter(void)
{
 Node *tempPtr = next;
 if(next == NULL)
  return NULL;
 next = tempPtr->next;
 return tempPtr;
}

#include "Node.h"
#include <fstream>
using namespace std;


int main(void)
{

 Node* head;
 Node* p=NULL;
 Node* q;
 Node* i;
 int data;

 ifstream ifile;
 ifile.open("list_input.txt");
 while(!ifile.eof())
 {
  ifile >> data; // data에 정수 하나를 넣는다
  i = new Node(data,NULL); // 대입
  if(p==NULL) 
  {
   p=i;head=p;
  }
  else 
  {
   p->InsertAfter(i);
   p=p->next;
  }
  
  i=NULL;  
 } // 대입 완료

 
 for(Node* n=head;n!=NULL;n=n->next) // 뒤집기 전 출력
 {
  cout << n->data << " ";
 }
 cout << endl;
  

 // 뒤집기 시작
 p=head;
 q=NULL;
 while(p)
 {
  i = q; // 임시로 저장한다
  q = p; // 다음 링크를 대입
  p = p->next; // 다다음 링크를 대입
  q->next = i; // next에 이전 링크 포인터를 대입
 }

 head= q;
 

 for(Node* n=head;n!=NULL;n=n->next) // 뒤집기 후 출력
 {
  cout << n->data << " ";
 }
 cout << endl;



 return 0;
}