逆置/反轉單連結清單

思路：摘結點法

//逆置/反轉單連結清單
#include<iostream>
using namespace std;

typedef int DataType;
typedef struct SListNode
{
  DataType data;            //資料
  struct SListNode * next;   //指向下一個結點的指針
}SListNode;

SListNode* CreateNode(DataType x)  //創造結點
{
  //1.先開辟空間 2.資料賦給data 3.指針置空
  SListNode* NewNode = (SListNode *)malloc(sizeof (SListNode));
  NewNode->data = x;
  NewNode->next = NULL;

  return NewNode;
}

void PushBack(SListNode * &ppHead, DataType Data)
{
  //1.none 2.one and more
  if (ppHead == NULL)
  {
    ppHead = CreateNode(Data);
  }
  else
  {
    //1.先找到尾結點 2.把新節點鍊起來
    SListNode* cur = ppHead;
    while (cur->next)
    {
      cur = cur->next;
    }
    cur->next = CreateNode(Data);

  }
}
//列印
void PrintSNodeList(SListNode *&ppHead)
{
  while (ppHead)
  {
    printf("%d->", ppHead->data);
    ppHead = ppHead->next;
  }
  cout << "NULL" << endl;
}

//逆置/反轉單連結清單
SListNode* ReverseList(SListNode*& pHead)
{
  //摘結點法
  SListNode* cur = pHead;  
  SListNode* newHead = NULL;  //建立一個新頭結點
  while (cur)
  {
    SListNode* tmp = cur;  //tmp指向cur
    cur = cur->next;    //cur指向下一個
    tmp->next = newHead;    //1.第一次tmp->next=NULL 2.以後每次利用tmp把結點和newHead連起來
    newHead = tmp;   //再把頭結點向前移
  }
  return newHead;

}
void Test()
{
  SListNode* pHead = NULL;
  PushBack(pHead, 1);
  PushBack(pHead, 2);
  PushBack(pHead, 3);
  PushBack(pHead, 4);
  PushBack(pHead, 5);
  PushBack(pHead, 6);
  PushBack(pHead, 7);
  PushBack(pHead, 8);
  SListNode* newHead=ReverseList(pHead);
  PrintSNodeList(newHead);
}

int main()
{
  Test();
  system("pause");
  return 0;
}