//【例2.4】  單鏈表逆轉。

#include "SinglyLinkedList.h"                  //單鏈表類
//#include "HSLinkedList.h"                        //帶頭結點的單鏈表類

template <class T>
void reverse(SinglyLinkedList<T> &list)          //將單鏈表逆轉，引用類型參數
{
    Node<T> *p=list.head, *front=NULL;           //front作為p結點的前驅結點
    while (p!=NULL)
    {
        Node<T> *q = p->next;                    //設置q是p的后繼結點
        p->next = front;                         //使p->next指向p結點的前驅結點
        front = p;
        p = q;                                   //p到達后繼結點
    }
    list.head = front;                           //改變單鏈表list的頭指針
}

/*
template <class T>
void reverse(HSLinkedList<T> &list)              //將帶頭結點的單鏈表逆轉
{
    Node<T> *p=list.head->next, *front=NULL;     //front作為p結點的前驅結點
    while (p!=NULL)
    {
        Node<T> *q = p->next;                    //設置q是p的后繼結點
        p->next = front;                         //使p->next指向p結點的前驅結點
        front = p;
        p = q;                                   //p到達后繼結點
    }
    list.head->next = front;                     //改變單鏈表list的頭指針
}
*/
int main()
{
    int table[]={1,2,3,4,5,6,7,8};
    SinglyLinkedList<int> list(table,8);                   //創建單鏈表

//    SinglyLinkedList<char> list("ABCDEFGH",8);             //創建單鏈表
//    HSLinkedList<char> list(table,8);                   //創建帶頭結點的單鏈表

    cout<<list;
    reverse(list);
    cout<<"逆轉后 "<<list;
    return 0;
}

/*
程序運行結果如下：
(1, 2, 3, 4, 5, 6, 7, 8)  
逆轉后  (8, 7, 6, 5, 4, 3, 2, 1)  

(A, B, C, D, E, F, G, H)  
逆轉后 (H, G, F, E, D, C, B, A)  

head┌─┬─┐  ┌─┬─┐  ┌─┬─┐  ┌─┬─┐  ┌─┬─┐ 
  →│1 │  ┼→│2 │  ┼→│3 │  ┼→│4 │  ┼→│5 │＾│ 
    └─┴─┘  └─┴─┘  └─┴─┘  └─┴─┘  └─┴─┘ 
*/