🌈键盘敲烂,年薪30万🌈
目录
普通单向链表
双向链表
带哨兵的链表
环形链表
⭐双向带头带环链表的实现⭐
⭐链表基础OJ⭐
普通单向链表
结点结构:只有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.链表环问题