面试题「单链表逆序」

2,878 阅读3分钟

本文为原创文章,如需转载请注明出处,谢谢!

扯淡

今天出去面试又碰到这题了,从毕业到现在面试这么多次,也碰上了不少次这道题,可见这题的重要性。然而面试前没复习这题,导致面试的时候底气不足,虽然思路说对了,但是还是对自己的表现不满意。原因就是算法题当时解出来的时候印象非常深刻,但是过后的工作中很少涉及,很容易淡忘。所以必须要总结,把每次面试的坑都总结下来,为之后的面试做准备。

正题

废话不说了,直接给大家看张我总结的思路图。

单链表逆序
单链表逆序

我们对照着图一步一步的分析,帮助大家记忆。

1.定义三个节点引用

我们用 java 语言实现就需要先定义三个节点引用,Prev表示上一个节点,Head表示当前节点,Next则表示下一个节点。然后让 Prev 指向 Null,Head 指向链表的头节点,Next 也指向 Null。

2.逆序过程

最重要的一步,这步会了,以后的步骤都是重复第一步,循环即可。

(1) 初始状态,Head—>A,Prev—>Null,Next—>Null。

(2) Next = Head.next,首先用 Next 引用缓存下一个节点,为什么这是第一步?因为如果先将 Head.next 逆序指向前面节点,下一个节点就丢了,就没有引用可以拿到下一个节点了。

(3) Prev = Head.next,再将当前节点的下一个节点指向 Head 前面的节点,完成逆序。

(4) 到现在为止,Prev—>Null,Head—>A(头结点),Next—>B,A.next—>Prev(Null)。然后,需要将 Prev 和 Head 都向右移动,即 Prev—>Head(A),Head—>Next(B)。这步操作完之后就得到了图中的第二条。

3.再来一遍

不明白第一步没关系,我们继续分析第二步。流程和 (1) 完全一致。

(1) 初始状态,Head—>B,Prev—>A,Next—>A(上一步中没对 Next 做操作,所以还是指向 A)。

(2) Next = Head.next。同样先缓存下一个节点,现在 Next—>C。

(3) Prev = Head.next,将当前节点的链和前一节点连接,现在 B.next—>Prev(A)

(4) 目前情况是,Prev—>A,Head—>B(头结点),Next—>C,B.next—>Prev(A),同样地,向右移动 Prev 和 Head,即 Prev->Head(B),Head—>Next(C)。完成之后就得到了图中的第三条。

4.再来一遍,重要的事说三遍

再重复一遍,要是还不知道过程我也没辙了~

(1) 初始状态,Head—>C,Prev—>B,Next—>B。

(2) Next = Head.next。缓存下一个节点,现在 Next—>D。

(3) Prev = Head.next,将当前节点的链和前一节点连接,现在 C.next—>Prev(B)

(4) 目前情况是,Prev—>B,Head—>C(头结点),Next—>D,B.next—>Prev(B),同样地,向右移动 Prev 和 Head,即 Prev->Head(C),Head—>Next(D)。

5.伪代码

分析了这么多,我们知道了逆序的流程,得到如下伪代码:

Next = Head.next;
Head.next = Prev;//让链指向前节点
Prev = Head;//右移
Head = Next;

6.结束条件

循环终止的条件是什么呢?请看图中后两条,当只剩一个节点 E 没完成逆序的时候,还需要再重复一次刚才的步骤,向右移动 Prev 和 Head 后就得到了最后一条,看到 Head 指向了 Null(是右移 Head 的时候,Head—> Next,此时的 Next 为 E.next=Null)。所以判断条件为 while(Head != null)

7.完整代码

最后,附上完整代码。空间复杂度为 O(n)。

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null) return null;
        
    ListNode prev = null;
    ListNode next = null;
    
        while(head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

这次详细总结了以后,相信再面试再也不怕「单链表逆序」了!

我也是个初学者,如写的有问题,请及时联系我!感谢!