关于java:链表反转全家桶一动画详解单链表反转

44次阅读

共计 1309 个字符，预计需要花费 4 分钟才能阅读完成。

单链表的反转是一个 easy 级别的题目，这个题目在力扣上的提交次数达到 47 万次，而且在面试中也频频呈现，堪称是大受欢迎，它的兄弟们也跟着景色了。这道题自身是比较简单的，而它的“难兄难弟”就不是那么简略了。明天这篇文章先从简略开始，剖析单链表的反转。

题目形容如下。

反转一个单链表。

示例:

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

办法一：双指针迭代
迭代法在于，在遍历链表的过程中一一扭转链表节点的指向，重点在于在扭转节点指向的同时，不使链表产生断链。咱们能够应用两个变量 pre 和cur来示意以后拜访到的节点和前一个节点，要使 cur.next = pre，为了能使链表持续向前迭代，咱们还须要提前记录以后节点的下一个节点，并把下个节点赋值给cur 变量。
动画演示如下。

class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode node = cur.next;
            cur.next = pre;
            pre = cur;
            cur = node;
        }
        return pre;
    }
}

复杂度剖析

工夫复杂度：O(n)。
空间复杂度：O(1)。

办法二：递归
递归是个神奇的存在，那么简略，又那么简单，有时感觉它很近，实际上它却那么远，有时感觉重新认识了它，可它还是那个它，从未扭转过。每一次应用递归，都会对它了解更深一点。

递归法解决链表反转在于假如曾经反转好链表的其余节点，以后节点怎么解决。假如链表为

$$
N_1 \rightarrow N2 \rightarrow … \rightarrow N_k \rightarrow N_{k+1} \rightarrow … \rightarrow N_n
$$

如果 $N_{k+1}$ 到 $N_n$ 局部曾经反转实现，那么链表的构造是这个样子的：

$$
N_1 \rightarrow N2 \rightarrow … \rightarrow N_k \rightarrow N_{k+1} \leftarrow … \leftarrow N_n
$$

以后节点在 $N_{k}$ 的地位，为了使 $N_{k+1}$ 和 $N_k$ 的指向进行扭转，咱们要做如下操作：

$$
N_k.next.next = N_k
$$

代码如下：

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

链表反转应用递归，是让人感觉很惊艳的解法，但也不太好了解，上面借助动画慢放递归调用的过程。

复杂度剖析