反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

1.利用外部空间

主要思路：利用外部空间+STL算法

  1. 先申请一个动态扩容的数组或者容器，然后不断遍历链表，将链表中的元素添加到这个容器中。
  2. 再利用容器自身的 API，反转整个容器，这样就达到反转的效果了。
  3. 最后同时遍历容器和链表，将链表中的值改为容器中的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int divide(int dividend, int divisor) {
        int flag = 0;
        int count = 0;
        if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1;
        dividend = abs(dividend);
        divisor = abs(divisor);
        while (dividend - divisor >= 0) {
            dividend -= divisor;
            count++;
        }
        if (flag) count = -count;
        return count;
    }
};

2.双指针迭代

3.优化的双指针

4.递归