单链表反转

前言

今天继续说链表，常见的算法问题有以下几种：

• 单链表反转
• 两个有序的链表合并
• 删除链表倒数第n个结点
• 求链表的中间结点
• 链表中环的检测

之前说过链表从尾开始打印链表，有的朋友说和这个单链表反转还是有区别，所以今天就看看这个类似的问题：单链表反转。

题目：单链表反转

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

解法一

题目很简单，就是一个单链表，要求反转链表。

首先一个容易想到的办法就是遍历，每次把指针方向修改:

A —> B 改成 B —> A

但是在修改结点的next之前，必须更新之前的链表指向，否则就无法向后遍历，用图表示下：

public ListNode reverseList(ListNode head) {
        //新链表结点
        ListNode prev = null;
        //临时结点
        ListNode curr = head;
        //开始遍历
        while (curr != null) {
            //先设置一个临时链表结点
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

该算法中，有两个链表：

1、新链表prev，每次改变指向之后要更新链表的结点。

2、旧链表curr，要每次更新到当前结点的next。如上图所示。

• 开始遍历的时候，先设置一个临时链表结点指向当前结点的next，也就是上图说的情况，先记录下后面要遍历的链表结点。
• 然后开始反转当前结点指向新链表。
• 新链表更新到当前结点。
• 旧链表更新到next。

时间复杂度

由于用到了遍历，所以时间复杂度就是O(n)

空间复杂度

之前说过，链表操作并没有用到另外的n大小空间，只是多了几个类似指针的链表结点,也就是常量空间，操作的还是原来的地址空间，所以空间复杂度为O(1).

解法二

还有个办法就是递归，之前说过只要遇到重复操作并且有终止条件，就可以用到递归。

那我们就先来找找这其中的重复工作。

由刚才的算法得知，从前面开始反转比较麻烦，那我们是不是可以先通过递归递到最后的结点，然后开始往前归呢？

比如先把结点递到最后一个数：

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        return p;
    }

这样递归之后，链表结点就来到了最后一个结点，然后开始往回归，也就是把每个结点的链表反转。

假如 A -> B，我们需要反转这两个结点，你能想到什么办法呢？

很简单：

B.next=A

那B是怎么算出来的呢？

A.next=B
B.next=A 
==>
A.next.next=A

反转的方法找到了，这也就是我们需要做的重复工作：

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        return p;
    }

但是还少了点啥？链表尾结点必须指向null，所以我们还需要再重复工作中加上在反转两个结点之后，再指向null的工作。

所以最后的算法就是：

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

再总结下这个递归方法：

• 递：把链表指针递到尾结点
  
• 归：从尾结点开始，每次反转相邻两个结点，并将尾结点指向null。

扩展：

其实递归方法在我们程序设计中也常常被用到。比如设计模式中的 责任链模式，就是用到了递归思想。在Okhttp的拦截器源码中就有体现～

时间复杂度

递和归相当于遍历了两次，所以时间复杂度是O(n)

空间复杂度

对于递归方法，要记住的是：

在任何时间点内存中可能存在的最大堆栈帧数等于递归树的最大深度

因为递归算法中，每个调用的方法都会生成对应的堆栈帧，保存在内存中，并且只要对这个方法的调用没有终止，那么堆栈帧就无法被释放。

从逻辑上讲，进程的堆栈是由多个堆栈帧构成的，其中的每个堆栈帧都对应一个函数调用。当函数调用发生时，新的堆栈帧被压入堆栈；当函数返回时，相应的堆栈帧从堆栈中弹出。

所以该递归方法的空间复杂度最大为O(n)。

参考

https://www.cnblogs.com/cheetos/p/5405589.html 

https://time.geekbang.org/column/article/41149 

https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/