链表是什么

链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

为啥要讲

剑指OFFER67个问题中搜索链表，一共是8道相关的题，占比为11.9%。日常技术面试中反转链表、打印链表及各种变形常见到没法子不能再常见了。

而且链表和数组是基础数据结构，相对数组来说链表逻辑上更复杂一些，可以用来考察技术基本功。

比如Java面试必问题HashMap，实际存储就是数组+链表的组合，无论如何都是一个绕不过的问题。

链表解析

拿一个把数组转换成链表的小例子说一下链表的使用和数据结构。

  • 先定义一个最简单的单向链表，这个链表只有简单的一个Next指针

    1
2
3
4
5
6
7

    public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

  • 写一个数组转成链表的小函数

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    public ListNode arrayToListNode(int[] s) {
    ListNode root = new ListNode(s[0]);
    ListNode other = root;
    for (int i = 1; i < s.length; i++) {
        ListNode temp = new ListNode(s[i]);
        other.next = temp;
        other = temp;
    }
    return root;
}

    详细解释一下这个函数的操作过程：

    • 先声明一个root对象，这个对象的指向内存的指针假如是400
    • 再声明一个中转阶段other，此时other和root都是同一个指针400，指向实际的一个内存对象
    • 第一次for遍历时候，先创建一个临时对象temp，指向指针为401的一个内存对象
    • 将401这个指针关联到指针400的next上，这时候root=other，即 400.next=401，此时401.next为空
    • 循环中最后一步将other的指针从400切换为401，即此时root还是400那个对象，root的next为指针401的那个对象
    • 第二次for循环时候，创建一个指针为402的对象temp
    • 将401的next指向402，即此时root的状态为400.next=401，而此时401.next=402，形成的链表即为400->401->402
    • 循环的最后一步又将other指针切换为402
    • 第三次for循环，创建一个指针为403的对象temp
    • 将402的next指向403，即即此时root的状态为400.next=401，401.next=402，402.next=403，形成的链表即为400->401->402->403

  • 经过函数若干次循环后，root最终就会是将一个{400, 401, 402, 403, 404, 405}这样的数组转换为400->401>402->403->404->405的链表结构

循环过程如图所示

链表循环过程