# [introduction to algorithm 05] print linked list from end to end

2021dragon 2021-09-15 07:58:17

## Core test points ： List related , Multi structure mixed use , recursive

Enter the head node of a linked list , Return the value of each node from the end to the end of the linked list （ Return with array ）. Analysis 1 ：（ Do not advocate ）
We can traverse the nodes in the linked list in turn through the given head node , And store the traversed node values in the array , At this time, the values of each node from beginning to end of the linked list are stored in the array , Then we invert the array to get the value of each node from the end to the end of the linked list .

``````/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */
class Solution {

public:

vector<int> v;
// Put the data in the linked list into the container from beginning to end v among
while (head != NULL)
{

}
// The container v Reverse
reverse(v.begin(), v.end());
return v; // Return to container v
}
};
``````

Analysis 2 ：（ More advocate ）
We can only traverse the chain from the header node to the tail node , But the problem requires us to return the value of each node from the end to the end of the linked list , In other words, the node value we traverse first should be output later , What do you think of at this time ？ Stack, of course , Stack is a first in and last out container .
We stack the traversed node values in turn , After traversal, pop up the data in the stack and put it into the array in turn .

``````/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */
class Solution {

public:

stack<int> st;
// Put the traversed node values on the stack in turn
while (head != NULL)
{

}
vector<int> v;
// The data in the stack is out of the stack in turn , Store in container v among
while (!st.empty())
{

v.push_back(st.top());
st.pop();
}
return v; // Return to container v
}
};
``````

Analysis three ：（ Positive solution ）
For this topic , We can also use recursion to solve . The process in the recursive function is set to recursive first 、 Re print , This gives priority to recursion , The node values are printed successively until the recursion returns .
Of course , Every recursive function has a condition for the end of recursion , Here, the condition for the end of recursion is to encounter a null pointer , At this point, the recursive traversal of the linked list ends . After recursion, the recursive function will return one by one , In the return process, node values will be printed one by one , The direction of recursive return is from the end of the chain list to the head of the chain , Therefore, the order of printing node values is from end to end . ``````/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */
class Solution {

public:

vector<int> v;
dfs(v, head); // Output recursively
return v;
}
// Recursive function
void dfs(vector<int>& v, ListNode*& pNode)
{

if (pNode == NULL) // The incoming node address is empty , Flag for the end of recursion
return;
dfs(v, pNode->next); // Recursion first
v.push_back(pNode->val); // After recursion （ meet NULL return ） Then output the node value
}
};
``````
Please bring the original link to reprint ,thank