利用栈实现反转

在原本链表的数据结构之外，引入一个栈（数组也可），将单链表循环遍历，将所有结点入栈，最后再从栈中循环出栈，记住出栈的顺序，得到的就是反转后的单链表。

实现如下：

    public Node reversalWithStack(Node head) {
        if (head == null || head.getNext() == null) {
            return head;
        }
        Stack stack = new Stack();
        while (head != null) {//循环遍历入栈
            stack.push(head);
            head = head.getNext();
        }
        Node newHead = (Node) stack.pop(); //头结点不动
        Node cur = newHead;
        while (!stack.isEmpty()) {
            Node popNode = (Node) stack.pop();//依次出栈
            cur.setNext(popNode);//cur依次移动，建立链接关系
            cur = popNode;
        }
        cur.setNext(null);//cur指针结束时一定要指向null,不然最后两个节点会相互引用的
        return newHead;
    }

但是这样实现，有一个问题，它会额外消耗一个栈的内存空间，此时空间复杂度就变成了 O(n)。

空间复杂度为 O(1) 反转

在排序算法中，有一个概念叫原地排序，指的是不需要引入额外的存储空间，在原数据结构的基础上进行排序。这种排序算法的空间复杂度是 O(1)。例如我们常见的冒泡排序、插入排序都是原地排序算法。

这里，我们也可以在原单链表的数据结构上，进行单链表反转。

递归方式

先假设后面链表都已经反转了，并把后面链表看成一个反转节点，那么只需要将当前节点和递归节点两个节点进行反转即可。

//递归方式
	public ListNode reverse(ListNode head) {
		if(head==null || head.next==null) {//递归终止条件是当前为空，或者下一个节点为空
			return head;
		}
		ListNode last = reverse(head.next);
		head.next.next = head;
		head.next = null;//防止链表循环，需要将head.next设置为空
		return last;//每层递归函数都返回last，也就是最后一个节点
	}

看起来有点不好理解，我们来步步拆解：
假设我们要反转这个链表

那么输入 reverse(head) 后，会在这里进行递归：

ListNode cur = reverse(head.next);

不要跳进递归（你的脑袋能压几个栈呀？），而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：

这个 reverse(head.next) 执行完成后，整个链表就成了这样：

并且根据函数定义，reverse 函数会返回反转之后的头结点，我们用变量 last 接收了。

现在再来看下面的代码：

head.next.next = head;

接下来：

head.next = null;
return last;

这样整个链表就反转过来了！递归代码就是这么简洁优雅。

这里有两个地方需要注意：

递归函数都要有递归出口，也就是这句：

		if(head==null || head.next==null) {//递归终止条件是当前为空，或者下一个节点为空
			return head;
		}

意思是如果链表只有一个节点的时候反转也是它自己，直接返回即可。

当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null

		head.next = null;//防止链表循环，需要将head.next设置为空

非递归方式

双指针迭代
我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。

动画演示如下：

动画演示中其实省略了一个tmp变量，这个tmp变量保存cur的下一个节点。

当我们要对一个结点进行指针翻转的时候，我们需要知道三个结点

待翻转的结点 cur
待反转结点的前驱结点 prev
待反转结点的下一个节点 tmp

 //非递归方式
	public ListNode reverseList(ListNode head) {
		ListNode pre = null;//申请节点，pre和 cur，pre指向null
		ListNode cur = head;
		ListNode tmp = null;
		while(cur!=null) {
			tmp = cur.next;//记录当前节点的下一个节点
			cur.next = pre;//然后将当前节点指向pre
			pre = cur;//pre和cur节点都前进一位
			cur = tmp;
		}
		return pre;
	}

数组存储

上面几种写法，都是基于单链表的数据是用链地址存储的，如果以数组形式存储数据，则可以用反转字符串的方法来实现反转！

    public void reverseWithArray(char[] originArray) {
        int from = 0;
        int to = originArray.length - 1;
        while (from < to) {//依次反转
            char tmp = originArray[from];
            originArray[from++] = originArray[to];
            originArray[to--] = tmp;
        }
    }