剑指 Offer 06. 从尾到头打印链表

评论(7)

• 杨帆 普通 2022年11月1日 下午4:29

  public int[] reversePrint(ListNode head) {
  int len = 0;
  ListNode cur = head;
  while(cur != null){
  cur = cur.next;
  len++;
  }
  int[] a = new int[len];
  int num = 1;
  cur = head;
  while(cur != null){
  a[len-num] = cur.val;
  num++;
  cur = cur.next;
  }
  return a;
  }

  时间复杂度：O(n)
  额外空间复杂度：O(1)

  登录以回复
• lobort 普通 2022年10月26日 下午7:06

  class Solution {
  public int[] reversePrint(ListNode head) {
  //方法一 创建指针遍历得到链表的长度 新建一个数组 从尾开始增加链表的值 注意数组的长度和元素的下表不要出错！！
  if(head == null){
  return new int[0];
  }
  int count = 0;
  ListNode temp = head;
  while(temp!=null){
  temp = temp.next;
  count++;
  }
  int [] res = new int[count];
  int k = count -1;
  while(head!=null){
  res[k–] = head.val;
  head = head.next;
  }
  return res;
  
  
  //方法二：利用栈先进后处的特点来完成 stack.add()增加元素 stack.pop()弹出栈内最上面的元素
  Stack st = new Stack();
  int count = 0;
  while(head!=null){
  st.add(head.val);
  head = head.next;
  }
  int [] res = new int[st.size()];
  for(int i =0; i <res.length; i++){
  res[i] = st.pop();
  }
  return res;
  }
  }
  

  登录以回复
• lobort 普通 2022年10月26日 下午7:05

  “`java
  class Solution {
  public int[] reversePrint(ListNode head) {
  //方法一 创建指针遍历得到链表的长度 新建一个数组 从尾开始增加链表的值 注意数组的长度和元素的下表不要出错！！
  if(head == null){
  return new int[0];
  }
  int count = 0;
  ListNode temp = head;
  while(temp!=null){
  temp = temp.next;
  count++;
  }
  int [] res = new int[count];
  int k = count -1;
  while(head!=null){
  res[k–] = head.val;
  head = head.next;
  }
  return res;

  //方法二：利用栈先进后处的特点来完成 stack.add()增加元素 stack.pop()弹出栈内最上面的元素
  Stack st = new Stack();
  int count = 0;
  while(head!=null){
  st.add(head.val);
  head = head.next;
  }
  int [] res = new int[st.size()];
  for(int i =0; i <res.length; i++){
  res[i] = st.pop();
  }
  return res;
  }
  }

  登录以回复
• cxc 普通 2022年10月24日 下午11:55

  class Solution {
      List<Integer> list = new ArrayList();
      public int[] reversePrint(ListNode head) {
          recur(head);
          int[] res = new int[list.size()];
          for(int i=0;i<res.length;i++){
              res[i] = list.get(i);
          }
  
          return res;
      }
  
      public void recur(ListNode head) {
          if(head == null) return;
          recur(head.next);
          //递归的时候添加到list头
          list.add(head.val);
      }
  }
  

  登录以回复
• zjl 普通 2022年10月24日 下午7:14

  递归。但是list怎么能直接取出数组？

      public int[] reversePrint(ListNode head) {
          List<Integer> list = new ArrayList();
          addNode(head,list);
          int[] arr = new int[list.size()];
          for(int i = 0 ; i < arr.length;i++){
              arr[i] = list.get(i);
          }
          return arr;
  
      }
      public void addNode(ListNode node , List<Integer> list){
          if(node==null){
              return;
          }
          addNode(node.next,list);
          list.add(node.val);
      }
  

  登录以回复
• 🚲南下 普通 2022年10月24日 上午10:37

  复杂度分析：
  时间复杂度：O(n)
  空间复杂度：O(1)

  class Solution {
  public:
      vector<int> reversePrint(ListNode* head) {
          int counter = 0; //之前忘记赋初值
          ListNode* pre = head;
          while(pre!=nullptr){
              counter++;
              pre = pre->next;
          }
  
          vector<int> A(counter); //定义数组接收
          while(head!=nullptr){
              // A.push_back(head->val);
              A[counter-1] = head->val; //从后往前赋值
              head=head->next;
              counter--;
          }
          return A;
  
      }
  };
  

  登录以回复
• Edison 普通 2022年10月23日 下午9:32

  思路一：先反转链表，再遍历，这样就不需要额外的栈空间开销

  class Solution {
  public:
      vector<int> reversePrint(ListNode* head) {
          //先反转链表，再遍历，这样就不需要额外的栈空间开销
          vector<int> ret;
  
          // 空链表
          if (head == nullptr) {
              return ret;
          }
  
          // 反转链表
          ListNode* cur = head->next;
          ListNode* temp;
          head->next = nullptr;
          while (cur) { // 遍历链表
              temp = cur->next;
              cur->next = head;
              head = cur;
              cur = temp;
          }
  
          // 直接尾插
          while (head) {
              ret.push_back(head->val);
              head = head->next;
          }
          // 返回ret数组
          return ret;
      }
  };
  

  方法二：使用栈

  class Solution {
  public:
      vector<int> reversePrint(ListNode* head) {
          vector<int> ret;
          stack<int> st;
          while (head) {
              st.push(head->val); //把链表元素全部放入栈中
              head = head->next;
          }
          while (!st.empty()) {
              ret.push_back(st.top()); // 把栈顶元素放到ret数组中
              st.pop();
          }
          return ret;
      }
  };
  

  方法三：就地逆序数组

  class Solution {
  public:
      vector<int> reversePrint(ListNode* head) {
          vector<int> ret;
  
          // 把链表所有元素尾插到ret数组中
          while (head) {
              ret.push_back(head->val);
              head = head->next;
          }
          int len = ret.size(); //统计元素个数
  
          // 交换第一个和最后一个，只需要交换len/2次
          for (int i = 0; i < len / 2; ++i) {
              swap(ret[i], ret[len-i-1]);
          }
          return ret;
      }
  };
  

  登录以回复