reverse.cpp

回顾基础

//【例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 │＾│ 
    └─┴─┘  └─┴─┘  └─┴─┘  └─┴─┘  └─┴─┘ 
*/