[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 ).
 Insert picture description here
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> printListFromTailToHead(ListNode* head) {

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

v.push_back(head->val);
head = head->next;
}
// 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:
vector<int> printListFromTailToHead(ListNode* head) {

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

st.push(head->val);
head = head->next;
}
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 .
 Insert picture description here

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

public:
vector<int> printListFromTailToHead(ListNode* head) {

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
Similar articles

2021-09-15

2021-09-15

2021-09-15