什么是链表

和数组一样，链表也是一种线性表

从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构

链表中的每一个内存块被称为节点 Node 。节点除了存储数据外，还需要记录链上下一个节点的地址，即后继指针 next。

链表的特点

插入、删除数据效率高，时间复杂度为 O(1)，只需要更改指针指向即可。

随机访问效率低，时间复杂度为 O(n)，需要从链头至链尾进行遍历。

和数组相比，链表的内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

常见的链表结构

单链表

每个节点只包含一个指针，即后继指针。

单链表有两个特殊的节点，即首节点和尾节点。

用首节点地址表示整条链表，尾节点的后继指针指向空地址 null 。

性能特点，插入和删除节点的时间复杂度为O(1)，查找的时间复杂度为O(n)。

循环链表

除了尾节点的后继指针指向首节点的地址外均与单链表一致。

适用于存储有循环特点的数据，比如约瑟夫问题。

双向链表

节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针 prev ）和下一个节点地址（后继指针 next ）。

首节点的前驱指针 prev 和尾节点的后继指针 next均指向空地址。

性能特点，和单链表相比，存储相同的数据，需要消耗更多的存储空间。

插入、删除操作比单链表效率更高，时间复杂度为 O(1) 。以删除操作为例，删除操作分为两种情况

  • 给定数据值删除对应节点

    单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为 O(n) 。

  • 给定节点地址删除节点

    要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历知道 p->next = q，时间复杂度为 O(n) ,而双向链表可以直接找到前驱节点，时间复杂度为 O(1) 。

  • 和单链表相比的优势

    对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次超找的位置 p ，每一次查询是，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

双向循环链表

首节点的前驱指针指向尾节点，为节点的后继指针指向首节点。

常见的链表操作

  • 单链表反转

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    private static Node reverseNode(Node head) {
        if (head == null || head.getNext() == null) {
            return head;
        }
      
        Node pre = null;
        Node cur = head;
        Node next = head.getNext();
        while (next != null) {
            cur.setNext(pre);
            pre = cur;
            cur = next;
            next = next.getNext();
        }
        cur.setNext(pre);
      
        return cur;
    }

  • 链表中环的检测

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public static boolean isCircleNodeList(Node head) {
        if (head == null) {
            return false;
        }
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.getNext() != null) {
            slow = slow.getNext();
            fast = fast.getNext().getNext();
            if (fast == null) {
                return false;
            } else if (slow == fast) {
                return true;
            }

        }
        return false;
    }

  • 两个有序链表合并

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    public static Node mergeNode(Node head1, Node head2) {
        Node guard = new Node(0);
        Node cur = guard;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                while (head1 != null && head1.val <= head2.val) {
                    cur.next = head1;
                    head1 = head1.next;
                    cur = cur.next;
                }
            } else {
                while (head2 != null && head2.val < head1.val) {
                    cur.next = head2;
                    head2 = head2.next;
                    cur = cur.next;
                }
            }
        }
        if (head1 != null) {
            cur.next = head1;
        }
        if (head2 != null) {
            cur.next = head2;
        }
        return guard.next;
    }

  • 删除链表倒数第 n 个节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public static Node deleteLastK(Node head, int K) {
        if (K < 1 || head == null) {
            return head;
        }
        Node guard = new Node(0);
        guard.next=head;
        Node slow = guard;
        Node fast = guard;
        for (int i = 0; i < K; i++) {
            if (fast!= null){
                fast=fast.next;
            }
        }
        while (fast != null && fast.next!= null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return guard.next;
    }

  • 求链表的中间节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public static Node findMiddle(Node head) {
        Node slow = head;
        Node fast = head;
        if (head == null || head.next == null) {
            return head;
        }
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }