剑指offer 从尾到头打印链表

剑指offer60天计划

Posted by liuwenzi on July 22, 2020
阅读数:

从尾到头打印链表


输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

题解

  • 翻转链表(在可修改输入的情况下,面试时需要问面试官是否可以修改输入)

    • 将链表翻转,然后逐个打印出来

    • 空间复杂度:O(n)

    • 时间复杂度:O(n)

    • Tips:翻转链表的时候注意各个节点的命名,否则容易弄混

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    
      /**
       * Definition for singly-linked list.
       * public class ListNode {
       *     int val;
       *     ListNode next;
       *     ListNode(int x) { val = x; }
       * }
       */
      class Solution {
          public int[] reversePrint(ListNode head) {
              if(head == null){
                  return new int[0];
              }
              int length = 1;
              ListNode middle = head.next;
              ListNode front = head;
              ListNode behind;
              head.next = null;
              while(middle != null){
                  length++;
                  behind = middle.next;
                  middle.next = front;
                  front = middle;
                  middle = behind;
              }
              int[] res = new int[length];
              int j = 0;
              ListNode next;
              while(front.next != null){
                  res[j++] = front.val;
                  next = front.next;
                  front = next;
              }
              res[j] = front.val;
              return res;
          }
      }	
    
    • H8avRi
  • 使用栈(利用栈的先进后出特点,在不可修改输入的情况下)

    • 按从前到后的顺序遍历链表,然后将链表的值入栈,然后在按出栈的顺序给到数组

    • 空间复杂度:O(n)

    • 时间复杂度:O(n)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      
      /**
       * Definition for singly-linked list.
       * public class ListNode {
       *     int val;
       *     ListNode next;
       *     ListNode(int x) { val = x; }
       * }
       */
      class Solution {
          public int[] reversePrint(ListNode head) {
              if(head == null){
                  return new int[0];
              }
              Stack<Integer> stack = new Stack();
              while(head.next != null){
                  stack.push(head.val);
                  head = head.next;
              }
              stack.push(head.val);
              int[] res = new int[stack.size()];
              int i = 0;
              while(!stack.isEmpty()){
                  res[i++] = stack.pop();
              }
              return res;
          }
      }		
      

      694tTY

  • 递归在本质上就是一个栈结构,可以使用栈也可以使用递归

    • 时空复杂度都为O(n)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      
      /**
       * Definition for singly-linked list.
       * public class ListNode {
       *     int val;
       *     ListNode next;
       *     ListNode(int x) { val = x; }
       * }
       */
      class Solution {
          private int length = 0;
          private int i = 1;
          private int[] res;
          public int[] reversePrint(ListNode head) {
              if(head == null){
                  return new int[0];
              }else{
                  recursion(head);
                  return res;
              }
          }
          void recursion(ListNode head){
              length++;
              if(head.next == null){
                  res = new int[length];
                  res[0] = head.val;
                  return;
          
              }else{
                  recursion(head.next);
                  res[i++] = head.val;
              }
          }
      }
      

      a8HBqZ


总结

  • 面试的时候做题记得限制条件,有些试题会要求不修改输入

  • 遇到可以用栈的题目也可以用递归,但是需要注意递归深度
  • 翻转链表记得规范节点命名,否则很容易弄混