牛客网《剑指Offer》之反转链表（Java实现）

输入：{1,2,3,4}
返回值：{4,3,2,1}

输入：{}
返回值：{}
说明：空链表则输出空    

假设未反转前的链表是如图所示

迭代方法反转链表是声明了1个结点空间来进行暂存1个结点空间进行返回新链表
因为反转之后NULL会在1的后面所以我们先声明一个前置结点存放一个NULL

 ListNode pre = null; 

然后从头结点开始进行迭代，当头结点不为空时，需要将当前结点保存到临时链表，因为如果直接让头结点的next等于pre的话，链表就断开了

ListNode current = head;

再将头结点的后续结点暂存到head,这样就成功分离了头结点和后续结点

head = head.next;

如图：第一次循环的debug结果可看出后续结点暂存到了head中

然后将当前结点的指针反转指向pre结点，current.next 就为 NULL 了

current.next = pre;

最后将当前结点值存入新链表前置结点pre，准备进入下一次迭代

pre = current;

一直迭代到head == NULL时，停止循环，输出pre即得到了反转链表

//迭代方法
    public static ListNode reverseList2(ListNode head) {
        ListNode pre = null;   //存上一个节点
        while (head != null) {
            //保存当前结点
            ListNode current = head;
            //保存当前结点的后续结点
            head = head.next;
            //重点 当前结点指向pre!!!!！！
            current.next = pre;
            //将当前结点存入前结点
            pre = current;
        }
        //返回pre指向的结点
        return pre;
    }

递归方法非常绕，最好是寻找到递归出口不然很容易把自己绕进去
先描述一下递归，递归就是函数在函数体中又调用自己。

如递归函数f(1)=1,f(n)=f(n-1)*n(n>1)

这里我假设n=5

f(5) = 5 * f(4)
f(5) = 5 * (4 * f(3))
f(5) = 5 * (4 * (3 * f(2)))
f(5) = 5 * (4 * (3 * (2 * f(1))))
即 f(5) = 120

然后看递归的代码，先执行第一行，不满足后，执行第二行递归函数
执行第二行后是调用本身，所以又进入第一行。一直执行到满足前面这个if条件即 head = null 或者 head.next ==null。

if (head == null  || head.next == null) return head;

假设当前链表为

即返回的这个head = 5->null
然后又会执行

 ListNode last = reverse(head.next);

执行这行代码之后的结果在debug中可看出,递归了四次，最后一次返回的新链表为5->null

再执行下一行代码后

 head.next.next = head;

再执行

head.next = null;
return last;

最后一次递归的结果return last给上一次递归，即只会执行下面四行了

ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;

这里head指向3是因为递归传值时传进去的head就为3开始的链表（可以参考前面的递归函数的例子）


再执行

head.next.next = head;
head.next = null;
return last;

可以看出 head 为 3 -> null ,last 为 5->4->3->null,然后依次返回递归结果最后输出的新链表last就是逆序的啦。

//递归方法
 public static ListNode reverseList(ListNode head) {
         if (head == null  || head.next == null) return head;
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

package learndatastructure;

import java.util.List;


public class ListNodeTest {
    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        public String show() {
            return this.val + "->" + (this.next == null ? "NULL" : this.next.show());
        }
    }
    
    public static ListNode reverseList2(ListNode head) {
        ListNode pre = null;   //存上一个节点
        while (head != null) {
            //保存当前结点
            ListNode current = head;
            //保存当前结点的后续结点
            head = head.next;
            //重点 当前结点指向pre!!!!！！
            current.next = pre;
            //将当前结点存入前结点
            pre = current;
        }
        //返回pre指向的结点
        return pre;
    }
    
    public static ListNode reverseList(ListNode head) {
        if (head == null  || head.next == null) return head;
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        System.out.println(a.show());
        System.out.println(reverseList(a).show());
    }
}