链表是什么

链表是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(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的链表结构

循环过程如图所示

链表循环过程