链表

链表的类型

接下来说一下链表的几种类型:

单链表

刚刚说的就是单链表。

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表既可以向前查询也可以向后查询。

如图所示：

循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

链表的定义

public class ListNode {

    public int val;
    public ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }

    // 循环打印
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        ListNode temp = next;
        stringBuilder.append(val);
        while (temp != null) {
            stringBuilder.append("->");
            stringBuilder.append(temp.val);
            temp = temp.next;
        }
        return stringBuilder.toString();
    }

}

链表的操作

删除节点

删除D节点，如图所示：

只要将C节点的next指针指向E节点就可以了。

添加节点

如图所示：

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

性能分析

再把链表的特性和数组的特性进行一个对比，如图所示：

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。

反转链表

双指针法

通过pre和cur两个指针互相转换的方式实现

/**
 * 双指针法
 *
 * @param head
 * @return
 */
public ListNode reverseList(ListNode head) {
    // 临时节点
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        // 记录当前节点的next
        ListNode next = curr.next;
        // 当前节点的next追加上prev的临时节点
        curr.next = prev;
        // prev节点换为当前节点
        prev = curr;
        // 当前节点换为下一个节点
        curr = next;
    }
    return prev;
}

头插法

通过不断将头结点拆出去，插入到节点上

/**
 * 头插法
 *
 * @param head
 * @return
 */
public ListNode reverseList(ListNode head) {
    ListNode pre = new ListNode(0);
    pre.next = null;

    // 头插法
    while (head != null) {
        // 暂存头结点的后续节点
        ListNode temp = head.next;
        // 头结点的后续节点为当前已经置换后的后续节点
        head.next = pre.next;
        // 将新的头结点接入到临时节点pre的next下
        pre.next = head;
        // 更新头节点
        head = temp;
    }

    return pre.next;
}