数据结构入门教程-单链表经典面试题分析

上节我们通过一个梁山好汉排行傍的案例分析了单链表的基本用法，这节我们通过一个经典的面试题来加深对单链表的学习，不扯了直接看正题

经典面试题

题目

• 单链表的反转问题

本片的讲解是基于我们对前面链表熟悉的基础上来加深印象，先来分析单链表是如何反转的，百度一大堆，但我个人绝得不适合像我这种入门的小白，下面是我的思路分析，先来看一张图：

单链表反转1.png

• 简单的讲解下：

1. 上面一行是我之前原来的链表，我经过某一种方式最后将链表反转成下面这个样子
   -我的思路：
   1). 首先我可以定义一个新的节点如：HeroNode reverseNode = new HeroNode();当然它只代表新的头结点，不做数据的任何存储.
   2). 接着从头到尾遍历原来的链表，每遍历一个节点将其取出并放在reverseNode头结点的next个，
   3). 将原来链表的head.next 指向reverseNode.next,这样就完成了链表的反转

看似简单的三步分析，但实际用代码实现还是有点难度的，接下来我们来看代码实现。

代码实现

//单链表反转
public static void reverseLinkList(HeroNode head){
    //首先是判断链表是否为null或者链表是否只有一个节点
    if (head.next == null || head.next.next == null){
        return;
    }
    //定义一个辅助指针(变量)，遍历原先的链表
    HeroNode cur = head.next;
    HeroNode next = null; //指向当前节点的下一个(主要做的原因是当我们遍历到当前节点cur时，需要取出当前节点，为了防止链表断开所以需要定义一个next来指向当前节点的下一个节点)
    HeroNode reverseHead = new HeroNode(0,"",""); //空的节点头
    //2.遍历原来的链表，每遍历一个节点，将其取出放在reverseHead的最前端
    while (cur !=null){
        next = cur.next;//先暂时的保存当前(cur)节点的下一个节点，主要的目的是后面的需要
        cur.next = reverseHead.next; //将当前节点的下一个节点指向reverseHead的下一个
        reverseHead.next = cur ; //将cur链接到新的链表中
        cur = next; //后移接着遍历
    }
    //将原来的head的下一个指向reverseHead的下一个节点实现单链表的反转
    head.next = reverseHead.next;


}

代码的关键是在while的循环里，就这样通过三步实现了链表的反转，因为链表反转是不包含头部节点的反转的，代码注释很详细，我们来看测试的过程：

测试代码

public class SingleLinkListCase {

  public static void main(String[] args) {
    //创建节点
    HeroNode node1 = new HeroNode(1,"宋江","及时雨");
    HeroNode node2 = new HeroNode(2,"卢俊义","玉麒麟");
    HeroNode node3 = new HeroNode(3,"吴用","智多星");
    HeroNode node4 = new HeroNode(4,"林冲","豹子头");
    //创建链表，并添加
    SingleLinkList singleLinkList = new SingleLinkList();
    singleLinkList.addOrderByNo(node1);
    singleLinkList.addOrderByNo(node4);
    singleLinkList.addOrderByNo(node2);
    singleLinkList.addOrderByNo(node3);
    //显示链表
    singleLinkList.show();

    //测试：链表反转测试
    System.out.println("反转之后============================");
    reverseLinkList(singleLinkList.getHead());
    singleLinkList.show();

测试结果如图所示：

image.png

上图是反转前后的对比，很显然，我们实现了链表的反转，世上算法万千，简单易懂的却在这里，嘻嘻嘻.....,同样这也是一道大厂的面试题