面试题 -- 从尾到头反向打印链表

旧城等待， 2022-08-25 02:22 133阅读 0赞

![SouthEast][]

以下代码在vs2010 测试通过：

/**
    *解题思路：
    *	方法一：从头遍历链表，把每次遍历得到的值存在一个栈中，然后在输出栈中的数字
    *	方法二：用递归的方法遍历链表，每次都先输出该节点的后一个节点
    *		(注)用递归的方法，如果链表很大，递归的层很深，可能会出现内存溢出，所以更好的方法是使用栈
    */
    #include "stdafx.h"
    #include "stdio.h"
    #include "stdlib.h"
    #define TRUE 1
    #define FALSE 0 
    
    typedef struct ListNode{
    	int value;
    	ListNode* next;
    }Node ;
    
    int createList(Node** list,int length);
    void reverseOrderList(Node* list);
    int _tmain(int argc, _TCHAR* argv[]){
    	Node* list = NULL;
    	Node* plist;
    	int result ;
    	result = createList(&list,8);
    	printf("原链表的顺序是：\n");
    	plist = list;
    	if(result == 1){
    		while(plist->next != NULL){
    			plist = plist->next;
    			printf("%d\t",plist->value);
    			
    		}
    	}
    	printf("\n反向链表的顺序是：\n");
    	Node* reverseList;
    	reverseList = list->next; //去掉头节点
    	reverseOrderList(reverseList);
    	system("pause");
    	return TRUE;
    }
    //创建一个单链表
    int createList(Node **list,int length){
    	Node* rootp;
    	Node* newNode;
    
    	if(*list == NULL)
    	*list = (Node*)malloc(sizeof(Node));
    	(*list)->value = length;
    	(*list)->next = NULL;
    
    	rootp = *list;
    	while(length > 0){
    		newNode = (Node*)malloc(sizeof(Node));
    		if(newNode == NULL){
    			return FALSE;
    		}
    		newNode->value = length;
    
    		rootp->next = newNode;
    		rootp = newNode;
    		length--;
    	}
    	newNode->next = NULL;
    	return TRUE;
    }
    /*
    * 用栈存储数字，实现反向链表的输出
    */
    int reverseOrderList(Node* pHead){
    	//建立一个空的栈
    	sqStack* s = NULL;
    	s = (sqStack *)malloc(sizeof(sqStack));
    	s->top = -1;
    	//入栈
    	while(pHead != NULL){
    		s->top++;
    		s->data[s->top] = pHead->value;
    		pHead = pHead->next;
    	}
    	//出栈
    	while(s->top != -1){
    		printf("%d\t",s->data[s->top]);
    		s->top-- ;
    	}
    	return TRUE;
    }  
    */
    /*
    *用递归的方法，反向输出链表
    */
    void reverseOrderList(Node* list){
    
    	if(list != NULL){
    		if(list->next != NULL){
    			reverseOrderList(list->next);
    		}
    	}
    	
    	printf("%d\t",list->value);
    }

[SouthEast]: /images/20220824/b479dc473cb94534a7b5e83ad5fbb465.png