# 链表

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续

# 分类

单向
双向
循环

# 使用的对象

public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

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

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        public static ListNode of(int... val) {
            ListNode res = new ListNode(-1, null);
            ListNode p = res;
            for (int i : val) {
                while (p.next != null) {
                    p = p.next;
                }
                p.next = new ListNode(i, null);
            }
            return res.next;
        }

        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder("[");
            ListNode next = this;
            while (next != null) {
                stringBuilder.append(next.val).append(",");
                next = next.next;
            }
            stringBuilder.delete(stringBuilder.length() - 1, stringBuilder.length());
            stringBuilder.append("]");
            return stringBuilder.toString();
        }
    }

# 单向链表

核心方法

add
addFirst
removeFirst
remove

重要的思想就是指针以及在操作的时候避免空指针

创建Node对象分别记录下一个地址和值

static 什么时候加

static 加和不加的时机在于，处理的值是否依赖于外部，如果依赖于外部那么就不能加static

    public static class Node {
        private int value;

        private Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }

        public Node(int value) {
            this(value, null);
        }

        public int getValue() {
            return value;
        }

        public Node getNext() {
            return next;
        }
    }

add & addFirst


public void addFirst(int value) {
    head = new Node(value, head);
}

public void addLast(int value) {
    Node last = findLast();
    if (last == null) {
        addFirst(value);
        return;
    } else {
        last.next = new Node(value);
    }
}

remove

public boolean removeFirst() {
    if (head == null) {
        return false;
    }
    if (head.next == null) {
        head = null;
        return true;
    }
    head = head.next;
    return true;
}

# 双向

在单向链表上增加了一个pre节点，核心操作新增和删除，就是将上一个节点赋值next 赋值到当前节点当前节点的上一个节点，就是上一个节点

  private Node head;
    private Node tail;

    public RoundLinkList() {
        this.head = new Node(null, -1, null);
        this.tail = new Node(null, -1, null);
        head.next = tail;
        tail.pre = head;
    }

    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != tail; p = p.next, i++) {
            if (index == i) {
                return p;
            }
        }
        return null;
    }

    public void add(int value) {
        Node pre = tail.pre;
        Node node = new Node(pre, value, tail);
        pre.next = node;
        tail.pre = node;
    }

    public void insert(int index, int value) {
        Node node = findNode(index - 1);
        if (node == null) {
            throw new RuntimeException(index + "");
        }
        Node pre = node.next;
        Node inserted = new Node(node, value, node.next);
        node.next = inserted;
        pre.pre = inserted;
    }

    public boolean remove(int index) {
        Node node = findNode(index - 1);
        if (node == null) {
            throw new RuntimeException(index + "");
        }
        Node nextNext = node.next.next;
        if (nextNext == tail) {
            throw new RuntimeException(index + "");
        }
        node.next = nextNext;
        nextNext.pre = node;
        return true;
    }

    @Override
    public Iterator<Node> iterator() {
        return new Iterator() {
            Node p = head;
            @Override
            public boolean hasNext() {
                p = p.next;
                return p != tail;
            }

            @Override
            public Node next() {
                return p;
            }
        };
    }

    class Node {
        Node pre;
        int value;
        Node next;

        public Node(Node pre, int value, Node next) {
            this.pre = pre;
            this.value = value;
            this.next = next;
        }

    }

}

# 单向链表反转

# 方式一

每次新增内容往覆盖原有头部，让next指针指向原先头部，达到反转

public ListNode reverse(ListNode listNode) {
    ListNode newHead = null;
    while (listNode != null) {
        newHead = new ListNode(listNode.val, newHead);
        listNode = listNode.next;
    }
    return newHead;
}

# 方式二

跟方式一类似，区别在于将原先节点移除到新链表节点，完成后就是倒叙的，好处就是不会产生新的节点

提供一个容器类

public class List {
    private ListNode head;

    public List(ListNode head) {
        this.head = head;
    }

    public void addFirst(ListNode listNode) {
        listNode.next = head;
        head = listNode;
    }

    public ListNode removeFirst() {
        ListNode first = head;
        if (first == null) {
            return null;
        }
        head = head.next;
        return first;
    }

}

循环添加

public ListNode reverse(ListNode listNode) {
    List l1 = new List(listNode);
    List l2 = new List(null);
    while (true) {
        ListNode listNode1 = l1.removeFirst();
        if (listNode1 == null) {
            break;
        }
        l2.addFirst(listNode1);
    }
    return l2.head;
}

# 方法3

递归

public ListNode reverse(ListNode p) {
    if (p == null || p.next == null) {
        return p;
    }
    ListNode last = reverse(p.next);
    p.next.next = p;
    p.next = null;
    return last;
}

反转递归实现理解图

# 方法4

设置三个指针

O1：传入的链表
02：O1的下一个指针
N1：N1永远不动，指向头节点

/**
     * 每一次循环完的变化
     * 2 1 3 4 5 6
     * 3 2 1 4 5 6
     * 4 3 2 1 5 6
     * 5 4 3 2 1 6
     * 6 5 4 3 2 1
     */
    public ListNode reverse(ListNode o1) {
        ListNode o2 = o1.next;
        ListNode n1 = o1;

        while (o2 != null) {
            //将中间的指针断开，也就是o2的位置
            o1.next = o1.next.next;
            //将o2的位置改变到头部
            o2.next = n1;
            //n1还原到头部地址
            n1 = o2;
            //o2指向下一个
            o2 = o1.next;
        }
        return n1;
    }

← AVL 树队列 →