牛客网-剑指offer-链表

 //输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
//class Solution {
//public:
//    vector<int> printListFromTailToHead(ListNode* head) {
//};

#include<windows.h>
#include<iostream>
#include<ctime>
#include<vector>
using namespace std;

struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
			val(x), next(NULL) {
        }
  };

ListNode* CreateList(int n);//创建链表
int rand_number_second();//产生随机数给链表赋值,秒级随机数
long rand_number_Millisecond();//产生随机数给链表赋值,毫秒级随机数
void print_list();
ListNode* printListFromTailToHead_1(ListNode* head) ;
vector<int> printListFromTailToHead(ListNode* head) ;


int rand_number_second()
{
	srand(time(NULL));
	return rand();

}
long rand_number_Millisecond()
{
	SYSTEMTIME sys;
	GetLocalTime(&sys);//GetLocalTime是一个Windows API 函数，用来获取当地的当前系统日期和时间。
	return sys.wMilliseconds;

}
//创建链表
ListNode* CreateList(int n)
{
	ListNode* list;
	list = (ListNode*)malloc(sizeof(ListNode));
	list->next = NULL;

	
	for(int i = 0;i < n;i++ )
	{
		ListNode* insert;
		insert = (ListNode*)malloc(sizeof(ListNode));
		
		insert->val = i;
		insert->next = list->next;
		list->next = insert;
	}

	return list->next;
}
//输出链表元素
void print_list(ListNode* p)
{
	ListNode *k;
	k = p;
	while(k !=NULL)
	{
		cout<<k->val<<" ";
		k = k->next;
	}
	cout<<"\n";
}
//逆序打印链表
//方法1：
ListNode *printListFromTailToHead_1(ListNode* head)
{
	ListNode* l;
	
	int length =  0;
	l = head;
	//获取链表的长度
	while(head != NULL)
	{
		length++;
		head = head->next;
	}

	int k = length;//记录链表的长度

	//new一个动态数组，用于逆序存放链表的值
	int* ArrayList = new int[length];
	for(;length > 0;length--)
	{
		ArrayList[length-1] = l->val;
		if(l->next != NULL)
		{
			l = l->next;
		}
		else
			break;	
	}
	//重新定义一个链表，将数组的值顺序存储进去
	ListNode* list_new;
	list_new = (ListNode*)malloc(sizeof(ListNode));

	ListNode* p;
	p = list_new;
	p->next = NULL;
	//将数组的值顺序存储进数组
	for(int i = 0;i < k;i++)
	{
		ListNode* list_new_insert;
		list_new_insert = (ListNode*)malloc(sizeof(ListNode));
		list_new_insert->val = ArrayList[i];
		p->next = list_new_insert;
		list_new_insert->next = NULL;
		p = list_new_insert;
	}

	delete []ArrayList;
	return list_new->next;
	
}
//方法2：
vector<int> printListFromTailToHead(ListNode* head) {
	//vector是一个能够存放任意类型的动态数组，能够增加和压缩数据
    vector<int> result;//声明一个int型向量result
	if (head == NULL) {
		return result;
	}
	ListNode *pNode = head;
	while (pNode != NULL) {
		result.push_back(pNode->val);//将链表的值存入result这个vector容器中
		pNode = pNode->next;
	}
	reverse(result.begin(), result.end());

	int nSize = result.size();  
	for(int i=0;i<nSize;i++)  
    {  
        cout<<result.at(i)<<"     ";  
    }  
    cout<<endl;  
	return result;


    }

int main()
{
	int n;
	cout<<"初始链表的成员数量：";
	cin>>n;

	ListNode* list;
	list = CreateList(n);
	cout<<"orginal list:"<<endl;
	print_list(list);

	printListFromTailToHead(list);
	/*ListNode* inverse_list;
	inverse_list = printListFromTailToHead_1(list);
	cout<<"inverse list:"<<endl;
	print_list(inverse_list);*/
	
	system("pause");
	return 0;
}