从尾到头打印链表-剑指06（链表-c）

痛定思痛。 2022-11-18 13:51 60阅读 0赞

题目：

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = \[1,3,2\]  
输出：\[2,3,1\]

限制：

0 <= 链表长度 <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
第一种思路：最容易想到，直接反转链表，然后存到数组中去。  
第二种思路：还有就是计算链表长度，然后遍历链表倒序存到数组中。

int* reversePrint(struct ListNode* head, int* returnSize){ 
    
        if(head == NULL)
        { 
            *returnSize = 0;
            return NULL;
        }
            
         int ncount = 0;
         struct ListNode* curr = head;
         struct ListNode* pre = NULL;
         while(curr != NULL)
         { 
             struct ListNode* pnext = curr->next;
             curr->next = pre;
             pre = curr;
             curr = pnext;
             ncount++;
         }
    
         int *res = (int *)malloc(sizeof(int)*ncount);
         *returnSize = ncount;
         int i = 0;
         while(pre)
        { 
            res[i++] = pre->val;
            pre = pre->next;
        }
        return res;
    }

第二种思路

int* reversePrint(struct ListNode* head, int* returnSize){ 
         if(head == NULL)
         { 
              *returnSize = 0;
              return NULL;
         }
         int ncount = 0;
         struct ListNode* curr = head;
         struct ListNode* pre = head;
         while(curr != NULL)
         { 
             ncount++;
             curr = curr->next;
         }
    
         int *res = (int *)malloc(sizeof(int)*ncount);
         *returnSize = ncount;
         int i = ncount;
         while(pre)
        { 
            res[i--] = pre->val;
            pre = pre->next;
        }
        return res;
    }

完整代码：

#include<stdio.h>
    #include<stdlib.h>
    typedef struct ListNode{ 
         struct ListNode* next;
         int val;
    }ListNode;
    void CreateList(ListNode* head, int n)
    { 
         ListNode* p;
         ListNode* rear = head;
         for(int i=1; i<=n; i++)
         { 
              p = (ListNode* )malloc(sizeof(ListNode));
              p->val = i;
              rear->next = p;
              rear = p;
         }
         rear->next = NULL;
    }
    void PrintList(ListNode* head)
    { 
         ListNode* p = head;
         while(p)
         { 
              printf("%d ", p->val);
              p = p->next;
         }
    }
    
    int* reversePrint(struct ListNode* head, int* returnSize){ 
         if(head == NULL)
         { 
              *returnSize = 0;
              return NULL;
         }
         int ncount = 0;
         struct ListNode* curr = head;
         struct ListNode* pre = head;
         while(curr != NULL)
         { 
             ncount++;
             curr = curr->next;
         }
    
         int *res = (int *)malloc(sizeof(int)*ncount);
         *returnSize = ncount;
         int i = ncount-1;
         while(pre)
        { 
            res[i--] = pre->val;
            pre = pre->next;
        }
        return res;
    }
    
    int main()
    { 
         ListNode* head;
         head = (ListNode* )malloc(sizeof(ListNode));
         head->next = NULL;
         CreateList(head, 3);
         //PrintList(head->next);
    
         int returnSize = 0;
         int *a = &returnSize;
         int *b = reversePrint(head->next, a);
    
         for(int i = 0; i < *a; i++)
         { 
              printf("%d ", b[i]);
         }
    
    }