编程知识 cdmana.com

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

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 
	}
};

版权声明
本文为[2021dragon]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/09/20210909133734372x.html

Scroll to Top