[c language] [sword finger offer article] - print linked list from end to end

Title Description

Enter the head node of a linked list , Return the value of each node from the end to the end （ Return with array ）.

---

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

---

ideas

Method 1 End filling array method

  The tail filling array method refers to the forward traversal of the linked list , Fill in the node data from the end of the array .

• Traverse the linked list for the first time , Calculate the length of the linked list size
• malloc Distribute size Size of memory
• Traversing the linked list for the second time , Get node data , And fill in the node data from the end of the array
• Last , Return the array .

Method 2 Recursive method

  Recursive method , First, it recurses to the end of the linked list , Then start to return , Each layer returned , Get the node data .

• Traverse the linked list for the first time , Calculate the length of the linked list size
• Allocate memory space
• Start recursively traversing the linked list
• Last return array

Method 3 Stack

  Stack , It has the characteristics of first in and last out , This problem can be well solved by using the stack principle .

• Build stack structure , And realize stack pressing 、 Out of stack and other functions
• First traverse the list , Calculate the length of the linked list
• Allocate memory space for the returned array
• Create stack space
• Traverse the list again , Push the node data into the stack in order
• Out of the stack , Save the stack elements in the return array
• Last , Returns an array of

Code implementation

Method 1 End filling array method

int* reversePrint(struct ListNode* head, int* returnSize){
    
    
    struct ListNode *ptr;
    int size = 0;
    int *arr = NULL;

    if(head == NULL)
    {
    
        *returnSize = 0;
        return NULL;
    }

    ptr = head;

    // First go through the linked list , Calculate the length of the linked list 
    while(ptr != NULL)
    {
    
        size++;
        ptr = ptr->next;
    }

    *returnSize = size;

    arr = (int *)malloc(sizeof(int)*size);
    if(arr == NULL)
    {
    
        printf("malloc failed!\n");
        *returnSize = 0;
        return NULL;
    }

    // Traverse the linked list again , Get node data 
    ptr = head;
    size--;

    while(ptr != NULL)
    {
    
        arr[size] = ptr->val;
        ptr = ptr->next;
        size--;
    }

    return arr;
}

Method 2 Recursive method

void recurve(struct ListNode* node , int *returnSize,int *arr)
{
    
    if(node == NULL)
    {
    
        return;
    }
    recurve(node->next,returnSize,arr);
    arr[(*returnSize)++] = node->val;
}

int* reversePrint(struct ListNode* head, int* returnSize){
    

    struct ListNode* ptr = NULL;
    int size;
    int *arr = NULL;

    if(head == NULL)
    {
    
        *returnSize = 0;
        return NULL;
    }

    // First traverse the list , Calculate the length of the linked list 
    ptr = head;
    while(ptr != NULL)
    {
    
        size++;
        ptr = ptr->next;
    }

    // Allocate memory space 
    arr = (int *)malloc(sizeof(int)*size);
    if(arr == NULL)
    {
    
        printf("malloc failed!\n");
        *returnSize = 0;
        return NULL;
    }

    *returnSize = 0;

    // Recursively traversing the list 
    recurve(head,returnSize,arr);

    return arr;
}

  Remember to put before recursion returnSize Initialize to 0*returnSize = 0;, otherwise returnSize Random value stored , There will be out of bounds operations during operation .

Method 3 Stack

struct stack{
    
    int top;
    int *list;
};

// Create stack space 
struct stack* create_stack(int size)
{
    
    struct stack *stk = NULL;
    
    if(size == 0)
    {
    
        return NULL;
    }

    stk = (struct stack *)malloc(sizeof(struct stack));
    if(stk == NULL)
    {
    
        return NULL;
    }
    stk->top = -1;

    stk->list = (int *)malloc(sizeof(int)*size);
    if(stk->list == NULL)
    {
    
        return NULL;
    }

    return stk;

}

// Stack pressing operation 
void stack_push(struct stack *stk,int val)
{
    
    if(stk == NULL)
    {
    
        return NULL;
    }
    stk->list[++(stk->top)] = val;
}

// Pop stack operation 
int stack_pop(struct stack *stk)
{
    
    if(stk == NULL)
    {
    
        return NULL;
    }
    return stk->list[(stk->top)--];
}

// Free up stack space 
void free_stack(struct stack *stk)
{
    
    if(stk == NULL)
    {
    
        return NULL;
    }

    free(stk->list);
    free(stk);
}

int* reversePrint(struct ListNode* head, int* returnSize){
    

    int size = 0;
    struct stack *mystack;
    struct ListNode* ptr = NULL;
    int *arr = NULL;
    int i = 0;

    if(head == NULL)
    {
    
        *returnSize = 0;
        return NULL;
    }

    // First traverse the list , Calculate the length of the linked list 
    ptr = head;
    while(ptr != NULL)
    {
    
        size++;
        ptr = ptr->next;
    }
    *returnSize = size;
 

    // Allocate the memory space of the returned array 
    arr = (int *)malloc(sizeof(int)*size);
    if(arr == NULL)
    {
    
        printf("malloc arr failed!\n");
        *returnSize = 0;
        return NULL;
    }
    // Allocate stack space 
    mystack = create_stack(size);
    
    // Traverse the list again , Push node data onto the stack 
    ptr = head;
    while(ptr != NULL)
    {
    
        stack_push(mystack,ptr->val);
        ptr = ptr->next;
    }
    
    // Pop up the data in the stack , Fill in the returned array 
    for(i = 0; i < size; i++)
    {
    
        arr[i] = stack_pop(mystack);
    }

    return arr;
}

  When implementing the spring stack algorithm , Pay attention to stk->top = -1;, It can skillfully avoid cross-border operation .