@[toc]

Synchronize GitHub here at 👉Github.com/TeFuirnever…

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup
  • Offer (C++ version) series: Offer 05 replace blank

1, dry

Print a linked list from end to end Enters the head node of a linked list and returns the value of each node from end to end (as an array). Example 1: input: head = [1,3,2] output: [2,3,1] limit: 0 <= list length <= 10000 pass count 242,193 submit count 322,163Copy the code

2. Auxiliary stack method

Note that the problem requires that the node values be printed in reverse order. This requirement can be implemented with the help of the stack.

Algorithm flow:

  1. Initialization: one array, one stack
  2. Push: Traverses the list, pushing the values of each node onto the stack.
  3. Off the stack: Pops each node value off the stack, stores it in an array and returns it.
  4. Returns an array of answers.
// Interview question 06. Print the linked list from end to end
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; * /
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        stack<int> stk;
        vector<int> res;
        while(head)
        {
            stk.push(head->val);
            head=head->next;
        }
        while(! stk.empty())
        {
            res.push_back(stk.top());
            stk.pop(a); }returnres; }};Copy the code

/* Time complexity: O(n). Traversing the list forward and then popping all the nodes off the stack is equivalent to traversing the list backward again. Space complexity: O(n). An additional stack is used to store each node in the linked list. * /
Copy the code

3, array simulation auxiliary stack method

You can implement stack functions through arrays.

Algorithm flow:

  1. Initialization: an array, simulated stack
  2. Push_back: Traverses the list, pushing the value of each node into the array.
  3. Returns an array of reverse answers.
// Interview question 06. Print the linked list from end to end
// Standard practice
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; * /
class Solution {
public:
	vector<int> reversePrint(ListNode* head) {
		vector<int> res;
		while (head)
		{
			res.push_back(head->val);
			head = head->next;
		}
		return vector<int>(res.rbegin(), res.rend()); }};Copy the code

4. Complexity

/* Time complexity: O(n). Iterate through the list forward. Space complexity: O(n). An additional array is used to store each node in the linked list. * /
Copy the code

— — — — — — — — — — — — — — — — — — —

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup
  • Offer (C++ version) series: Offer 05 replace blank

— — — — — — — — — — — — — — — — — — –

This article is supported by LeetCode, Niuke, the public ha Oh, Zhihu! Leetcode-cn.com/u/tefuirnev… blog.nowcoder.net/wsguanxl Mp.weixin.qq.com/s/bDwxwQfZy…

www.zhihu.com/people/tefu…