当前位置：首页 > news >正文

剑指offer之反转链表

news 来源：原创 2024/5/3 16:05:02

从尾到头打印链表

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

示例

输入

{67, 0, 24, 58}

返回值

[58, 0, 24, 58]

方法一

直接用简单粗暴的std::reverse()方法直接将List颠倒。

vector<int> printListFromTailToHead(ListNode* head){
  vector<int> res;
  while(head){
    res.push_back(head->val);
    head = head->next;
  }
  std::reverse(res.begin(), res.end());
  return res;
}

方法二

相对于一个数组取反过程，可以考虑使用入栈和出栈操作来实现，顺序读取链表元素存入栈，再将元素出栈存入数组中可以得到一个相反的ArryList，代码如下：

class Solution{
public:
  vector<int> printListFromTailToHead(ListNode* head){
    stack<int> s;
    vector<int> res;
    while(head){
      s.push(head->val);    //将元素入栈
      head = head->next;
    }
    while(!a.empty()){
      res.push_back(s.top); //读取栈顶元素存入vector
      s.pop();              //弹出栈顶元素					
    }
  }
};

方法三

考虑到可以使用反转链表的操作来实现。反转链表的精髓是定义三个指针head，pre，next。首先准备一个pre结点初始指向nullptr，表示正在反转结点的前一个结点，再准备一个cur，表示当前正在反转的结点，cur初始化为head。最后在准备一个next，表示还未反转的下一个结点。

使用如下示意图方便记忆，其中箭头表示等于：

代码如下：

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* next=cur;
        while(cur){
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        vector<int> st;
        while(pre){
            st.push_back(pre->val);
            pre = pre->next;
        }
        return st;
    }
};