想要精通算法和SQL的成长之路 - 反转链表

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 反转链表

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

思路如下 我们可以通过一次遍历修改链表节点的指针指向。由于指针修改的时候指针的引用就变了。我们需要用一个临时变量tmp来保存节点。同时我们需要一个变量pre来标识上一个节点。以及cur代表当前节点。

那么我们以上图为例原本的指针是 1 --> 2。我们要做的就是断开这个链接。然后将指针改为 2 --> 1。别看这个操作看似简单但是真正的实现需要分为如下几个步骤

1. 首先pre的值为nullcur的值就是链表头结点1。我们要提前存储2这个节点的引用后续指针改变了就拿不到了也就是 tmp = cur.next;
2. 然后将当前指针的next改为上一个节点。即反转的实现cur.next=pre;

这里其实就是相邻节点的一个指针反转了。但是我们既然要整个链表都反转我们就难以避免递归。因此我们还需要将cur和pre的指针往后移动。不断地循环上述操作。即

1. pre指针后移一位pre = cur;
2. cur指针后移一位cur = tmptmp是最开始存储的cur.next引用如图
   

循环终止条件cur当前指针不为null。最终完整代码如下

public ListNode reverseList(ListNode head) {
    ListNode cur = head, pre = null, tmp = null;
    while (cur != null) {
        // 1.临时存储下一个节点的引用
        tmp = cur.next;
        // 2.指针反转的核心步骤
        cur.next = pre;
        // 3.pre上一个指针往后移
        pre = cur;
        // 4.cur指针同样往后移进入下一次循环进行指针反转
        cur = tmp;
    }
    return pre;
}