🌈键盘敲烂，年薪30万🌈
普通单向链表
结点结构：只有val 和 next指针
初始时：head = null;
双向链表
指针：prev指针 val next指针
初始时：head = null;
带哨兵的链表
初始时：new 一个新节点sentinel val不重要，next = null
环形链表
尾节点的next指向头结点
初始时：头结点的next指向自己
⭐双向带头带环链表的实现⭐
准备工作
public class TheBestLinkedList implements Iterable<Integer>{ private Node sentinel = new Node(null, 666, null); public TheBestLinkedList() { sentinel.prev = sentinel; sentinel.next = sentinel; } private static class Node{ Node prev; int val; Node next; public Node(Node prev, int val, Node next) { this.prev = prev; this.val = val; this.next = next; } } @Override public Iterator<Integer> iterator() { return null; } }
addFirst
public void addFirst(int val){ Node newNode = new Node(sentinel, val, null); Node first = sentinel.next; newNode.next = first; first.prev = newNode; sentinel.next = newNode; }
addLast
public void addLast(int val){ Node newNode = new Node(null, val, sentinel); Node last = sentinel.prev; last.next = newNode; newNode.prev = last; sentinel.prev = newNode; }
removedLast
public Node removedLast(){ if(isEmpty()){ return null; } Node last = sentinel.prev; Node removedPrev = last.prev; sentinel.prev = removedPrev; removedPrev.next = sentinel; return last; }
removedFirst
public Node removedFirst(){ if(isEmpty()){ return null; } Node first = sentinel.next; // 只有一个节点 removedNext = sentinel Node removedNext = first.next; sentinel.next = removedNext; removedNext.prev = sentinel; return first; }
isEmpty
public boolean isEmpty(){ return sentinel.prev == sentinel; }
迭代器遍历
@Override public Iterator<Integer> iterator() { return new Iterator<Integer>() { Node p = sentinel.next; @Override public boolean hasNext() { return p != sentinel; } @Override public Integer next() { int ans = p.val; p = p.next; return ans; } }; }
⭐链表基础OJ⭐
1.反转链表
2.根据值删除链表
3.删除倒数第n个结点
4.有序链表去重
5.合并两个有序链表
6.合并多个有序链表
7.找链表中间结点
8.回文链表
9.链表环问题
