1. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

  1. 示例 1：
  3. 输入：s = "We are happy."
  4. 输出："We%20are%20happy."
  7. 限制：
  9. 0 <= s 的长度 <= 10000

思路：

  • 扫描字符串，每个字符进行拼接
  • 扫描时，判断字符是否为空格，如过是，那么就拼接 “%20” 
    class Solution {
  public String replaceSpace(String s) {
      StringBuilder sb = new StringBuilder();
      int length = s.length();
      for(int i=0;i<length;i++){  
          char tmp = s.charAt(i);
          if(tmp==' '){
              sb.append("%20");
              continue;
          }
          sb.append(tmp);
      }
      return sb.toString();
  }
}

    2. 从头到尾打印链表

    输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 ``` 示例 1：

输入：head = [1,3,2] 输出：[2,3,1]

<a name="77cn9"></a>
### 思路：
<a name="z5Asm"></a>
#### 方法一：使用栈结构

- 利用栈的 "先进后出" 的原则，实现排序的倒序；
- 遍历链表，将元素依次入栈，并进行计数（为后面创建数组做准备）；
- 循环进行出栈，依次给新建的数组进行赋值
- 返回数组
```java
class Solution {
    public int[] reversePrint(ListNode head) {
        // 使用栈结构的 “先进后出” 的原则
        Stack<Integer> stack = new Stack<>();
        ListNode temp = head;
        int count = 0;
        while(temp!=null){
            count++;
            stack.push(temp.val);
            temp = temp.next;
        }
        int[] res = new int[count];
        int j = 0;
        while(!stack.isEmpty()){
            res[j++] = stack.pop();
        }
        return res;
    }
}

方法二：使用递归

  • 新建一个方法，参数是传入一个链表节点，然后判断是否为空，如果为空，直接结束当前一层的递归

  • 进入新一层的递归，当最后一层递归完成进行返回，上一层进行往全局变量List中添加元素

    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;
  }
  private void recur(ListNode node){
      if(node==null){
          return;
      }
      recur(node.next);
      list.add(node.val);
  }
}

    方法三：正向遍历链表，反向给数组添加元素

  • 遍历依次链表，进行计数；

  • 以计数结果作为结果数组的长度，创建结果数组；
  • 遍历链表，从结果数组尾部进行元素添加。
    class Solution {
  public int[] reversePrint(ListNode head) {
      int count = 0;
      ListNode temp = head;
      while(temp!=null){
          count++;
          temp = temp.next;
      }
      int[] res = new int[count];
      temp = head;
      for(int i=count-1;i>=0;i--){
          res[i] = temp.val;
          temp = temp.next; 
      }
      return res;
  }
}