大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
成都创新互联网站建设公司一直秉承“诚信做人,踏实做事”的原则,不欺瞒客户,是我们最起码的底线! 以服务为基础,以质量求生存,以技术求发展,成交一个客户多一个朋友!专注中小微企业官网定制,成都做网站、成都网站制作,塑造企业网络形象打造互联网企业效应。
要反转一个单链表也就是使链表中的结点逆置,但并不是遍历链表每一次都将结点重新创建进行头插,这样就是重新创建一个单链表了而不是将原有的单链表逆置;因此,可以想到用多个指针来操控,既要防止找不到下一个结点的问题,也要解决逆置链表的链接问题;
程序设计如下:
#include#include using namespace std; template struct ListNode//链表结点结构 { T _data; ListNode * _next; }; template ListNode * buy_node(T data)//创建一个链表结点 { ListNode * tmp = new ListNode ; tmp->_data = data; tmp->_next = NULL; return tmp; } template void init_list(ListNode ** node, T data)//初始化链表 { *node = buy_node(data); } template void push_node(ListNode *& head, T data)//插入链表结点 { if(head == NULL) { init_list(&head, data); return; } ListNode * tmp = head; while(tmp->_next != NULL) { tmp = tmp->_next; } tmp->_next = buy_node(data); } template void print_list(ListNode * head)//打印链表 { while(head != NULL) { cout< _data<<"->"; head = head->_next; } cout<<"NULL"< void destroy_list(ListNode *& head)//销毁链表 { if(head != NULL) { ListNode * cur = head; ListNode * tmp = head; while(cur != NULL) { tmp = cur; cur = cur->_next; delete tmp; } head = NULL; } } template ListNode * ReverseList(ListNode * head)//逆置链表 { if(head == NULL)//条件判断 return head; ListNode * newHead = NULL; ListNode * cur = head; ListNode * tmp = head; while(cur != NULL) { tmp = cur;//将当前结点交给tmp cur = cur->_next;//指向当前结点的下一个结点,防止丢失找不到 tmp->_next = newHead;//使当前结点的next结点指向新的头结点完成头插 newHead = tmp;//更新链表的头结点 } return newHead; } int main() { ListNode * list = NULL; push_node(list, 1); push_node(list, 2); push_node(list, 3); push_node(list, 4); push_node(list, 5); push_node(list, 6); push_node(list, 7); push_node(list, 8); push_node(list, 9); cout<<"list: "; print_list(list); ListNode * newhead = ReverseList(list); cout<<"reverse list:"; print_list(newhead); destroy_list(list); return 0; }
运行程序:
《完》