链表的概念、实践和面试题

一、链表简介

链表是有序的列表，在内存中的存储方式如图：

• 链表是以节点的方式来存储，是链式存储；
• 每个节点包含data域，next指针（指向下一个节点）；
• 链表的节点不一定连续存储，是离散的状态；
• 链表分为带头节点的链表和没有头结点的链表，带头结点的逻辑结构示意图如下：
  

二、单链表的应用实例

2.1 单链表的基础方法的实现

使用带头结点的单向链表实现，完成对水浒英雄的CRUD。

• 普通新增方法
  此方法添加英雄时，直接添加到链表尾部。

1. 先创建一个head节点，不记录具体信息，作用就是表示单链表的头结点；
2. 此后每添加一个节点，就直接添加在链表的最后
3. 示意图：
   

• 按序新增方法
  此方法在添加英雄时，根据英雄的排名将英雄添加到指定的位置。

1. 首先找到新节点应该添加的位置，通过辅助指针来遍历找到位置；
2. 将新节点的next设置为指针指向节点的next节点；
3. 将指针指向的节点的next设置新节点；（2、3步骤顺序不能互换）
4. 不能添加相同排名的英雄；
5. 示意图：
   

• 修改节点方法

1. 先通过遍历找到对应节点；
2. 修改数据。

• 删除节点方法

1. 找到需要删除的del节点；
2. 将del节点的前一个节点的next指向del节点的next节点；
3. 示意图：
   

• 代码实现
  GitHub：https://github.com/goSilverhttps://img.qb5200.com/download-x/daydayup/blob/masterhttps://img.qb5200.com/download-x/datastructure/src/hanshunping/chapter04/SingleLinkedListDemo.java

2.2 单链表的相关面试题

• 求单链表中的有效节点的个数

思路：
遍历单链表，如果有头结点忽略头结点

代码：

    /**
     * 获取链表的长度
     *
     * @param head 链表头结点
     * @return 长度
     */
    int getLength(HeroNode head) {
        int length = 0;
        while (Objects.nonNull(head.getNext())) {
            length++;
            head = head.getNext();
        }
        return length;
    }

• 查找单链表中的倒数第k个节点
  思路：

1. 先求得链表的长度length；
2. 用length - k即可算出倒数第k个节点所处位置；
3. 从链表头结点遍历length - k次即可。

代码：

    /**
     * 寻找倒数第k个节点
     *
     * @param singleLinkedList 链表
     * @param k                k值
     * @return 倒数第k个节点
     */
    HeroNode findTheKthFromBottom(SingleLinkedList singleLinkedList, int k) {
        int length = getLength(singleLinkedList.head);
        int index = length + 1 - k;
        HeroNode temp = singleLinkedList.head;
        while (Objects.nonNull(singleLinkedList.head.getNext()) && index > 0) {
            temp = temp.getNext();
            index--;
        }
        return temp;
    }

• 反转链表

1. 定义一个新的头结点newHead；
2. 遍历原来的链表，每遍历一个节点，就将这个节点放到newHead的next即可；
3. 打印时以newHead为头结点打印。

示意图：

代码：

    /**
     * 反转链表
     * 思路：
     * 定义一个新的头结点newHead，遍历链表，依次将遍历的节点取出放到newHead的后面即可
     *
     * @param oldHead 链表的旧头结点
     */
    void reverse(HeroNode oldHead) {
        // 定义一个新的头结点
        HeroNode newHead = new HeroNode(0L, "", "");
        // 定义一个临时节点，记录即将遍历的下一个节点
        HeroNode next;
        // 跳过头节点
        HeroNode current = oldHead.getNext();
        while (Objects.nonNull(current)) {
            // 记录即将遍历的下一个节点
            next = current.getNext();
            // 将newHead的下一个节点设置为当前节点的next
            current.setNext(newHead.getNext());
            // 将newHead的next设置为当前节点
            newHead.setNext(current);
            // 恢复遍历指针
            current = next;
        }
        // 修改链表头结点
        head = newHead;
    }

• 从尾到头打印单链表
  思路：
  方式1：将单链表先进行反转操作，然后再遍历打印即可，缺点是会破坏原来的单链表的存储结构；
  方式2：可以利用栈数据结构先进后出的特性，从头到尾遍历时将节点依次压入栈中，打印时依次从栈中pop即可。

代码：

    /**
     * 逆向打印链表
     * 思路：
     * 1、先反转链表，再打印链表，缺点是会破坏原链表的结构
     * 2、利用栈数据结构先进后出的特性来辅助实现
     * 这里用栈来实现
     */
    void reversePrint() {
        Stack<HeroNode> nodeStack = new Stack<>();
        HeroNode current = head.getNext();
        while (Objects.nonNull(current)) {
            nodeStack.push(current);
            current = current.getNext();
        }
        while (!nodeStack.isEmpty()) {
            System.out.println(nodeStack.pop());
        }
    }