系列文章目录
目录
前言
本文通过单链表的模拟实现，帮助了解单链表的底层原理，以及常见的链表的常用操作，比如反转链表，找链表的中间节点等。模拟实现双向链表，了解双向链表的底层原理，以及 ArrayList 和 LinkedList 的比较。
一、模拟实现链表
链表是物理存储结构上非连续，逻辑上连续的存储结构；每个节点都会保存下一个节点的哈希值，通过这个节点可以找到下一个节点；
链表的属性：用 head 表示链表的头节点；
public class MySingleList {
static class ListNode{
public int val;
public ListNode next;
public ListNode(int val){
this.val = val;
}
}
public ListNode head;
// 链表的方法
// ...
}1. 遍历链表
以下方法都需要遍历一遍链表：
display(): void 打印节点信息；
size(): int 返回链表的长度；
contains(int key): boolean 判断链表中是否包含 key；
// 打印所有节点信息
public void display(){
ListNode cur = head;
while(cur != null){
System.out.print(cur.val + " ");
cur = cur.next;
}
}
// 求链表的长度
public int size(){
ListNode cur = head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
// 查找关键字 key 是否在链表中
public boolean contains(int key){
ListNode cur = head;
while(cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
2. 插入节点
addFirst(int data): void 头插法，将节点插入到链表头节点的位置；
addLast(int data): void 尾插法，将节点插入到链表尾节点的位置，尾插的时候要注意，当链表没有节点，即 head == null，这时候要注意将要插入的节点设置为头节点；
findIndexPrev(int index): ListNode 找到 index 位置节点的前驱；
addIndex(int index, int data): void 在 index 位置插入节点；
插入之前需要先判断 index 位置是否合法；
如果合法再判断一下是否是头插，是否是尾插，因为这俩方法已经写好了，可以调用；
找到要插入节点的前驱，找到前驱之后进行插入；
// 头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
// 尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
ListNode cur = head;
if(cur == null) {
this.head = node;
return;
}
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
// 在任意位置插入
public void addIndex(int index, int data){
if(index < 0 || index > size()){
throw new PosOutOfBoundsException(index + "插入位置不合法");
}
if(index == 0){
addFirst(data);
return;
}
if(index == size()){
addLast(data);
return;
}
ListNode cur = findIndexPrev(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
// 找到 index 下标的前一个节点
private ListNode findIndexPrev(int index){
ListNode cur = head;
while(--index > 0){
cur = cur.next;
}
return cur;
}3. 删除节点
remove(int key): void 删除第一个值为 key 的节点；
如果链表为空则直接返回；
如果头节点为要删除的节点，直接删除；
如果要删除的节点不存在，抛异常；
如果要删除在后面，先找到要删除节点的前驱，再删除；
findPrev(int key): ListNode 找到值为 key 的节点的前驱，没有要删除的节点，返回 null；
removeAll(int key): void 删除所有值为 key 的节点；
如果链表为空，直接返回；
从头节点后面开始删除，找到要删除的节点和它的前驱，进行删除；
删除完成后，当前节点指针向后移动；
如果没有找到要删除的节点，前驱和当前节点指针都同步向后移动；
最后判断头节点，如果头节点也是要删除的节点，进行删除；
// 删除节点
public void remove(int key){
if(head == null){
return;
}
// 单独删除头节点
if(head.val == key){
head = head.next;
return;
}
ListNode prev = findPrev(key);
if(prev == null){
throw new RuntimeException("要删除的节点不存在！");
}
ListNode del = prev.next;
prev.next = del.next;
}
// 找到 data 节点的前驱
private ListNode findPrev(int key){
ListNode cur = head;
while(cur.next != null){
if(cur.next.val == key){
return cur;
}
}
return null;
}
// 删除所有值为 key 的节点
public void removeAll(int key){
if(head == null){
return;
}
ListNode prev = head;
ListNode cur = prev.next;
while(cur != null){
if(cur.val == key){
prev.next = cur.next;
cur = cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
// 判断头结点
if(head.val == key){
head = head.next;
}
}4. 清空链表
clear(): void 清空链表，只需要将头结点置空即可；
// 清空链表
public void clear(){
this.head = null;
}二、链表的常见操作
1. 反转链表
reverseList(ListNode head): ListNode 反转链表；
如果链表为空，返回 null；
如果链表不为空，依次将 head 后面的元素进行头插；
public ListNode reverseList(ListNode head) {
if(head == null) return head;
ListNode cur = head.next;
head.next = null;
while(cur != null){
ListNode next = cur.next;
cur.next = head;
head = cur;
cur = next;
}
return head;
}2. 返回链表的中间节点
middleNode(ListNode head): ListNode 返回链表的中间节点，如果链表是奇数个元素，返回中间节点，如果链表是偶数个元素，返回右中点节点；
定义快慢指针，快指针每次走两步，慢指针每次走一步，如果快指针走到最后一个位置或者空位置，返回慢指针指向的节点即可；
public ListNode middleNode(ListNode head) {
if(head == null){
return head;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next;
fast = fast.next;
slow = slow.next;
}
return slow;
}3. 链表倒数第 k 个节点
findKthtoTail(ListNode head, int k): ListNode 找倒数第 k 个节点
先判断 head 是否为空，如果 head 为空，返回 null；
再判断 k 的值是否合法，如果不合法，返回 null；
定义快慢指针 fast 和 slow，先让 fast 走 k - 1步，再让 fast 和 slow 同时走， fast 走到尾巴节点的时候，slow 正好走到倒数第 k 个节点；
// 返回链表倒数第 k 个节点
public ListNode findKthToTail(ListNode head, int k){
if(head == null) return null;
if(k <= 0 || k > size()) return null;
ListNode fast = head;
ListNode slow = head;
while(--k > 0){
fast = fast.next;
}
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}4. 合并两个有序链表
mergeTwoLists(ListNode list1, ListNode list2): ListNode 合并两个有序链表
两个链表的元素相互比较，小的加入新的队列，指针后移；
当有一个链表为空了，开始把剩下的链表的元素按顺序加入到新的链表中；
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
ListNode newHead = new ListNode();
ListNode cur = newHead;
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
cur.next = list1;
list1 = list1.next;
}else{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
while(list1 != null){
cur.next = list1;
list1 = list1.next;
cur = cur.next;
}
while(list2 != null){
cur.next = list2;
list2 = list2.next;
cur = cur.next;
}
return newHead.next;
}5. 分割链表
要求：将小于 x 的节点排在其余节点之前，不改变原来节点的顺序；
partition(ListNode pHead, int x): ListNode 分割链表；
小于 x 的节点放 head1 后面，大于等于 x 的节点放在 head2 后面；
合并 head1 和 head2，返回新的链表；
注意：后面的链表的尾巴节点的 next 一定要置空，避免成环；
public ListNode partition(ListNode pHead, int x) {
if(pHead == null) return null;
ListNode head1 = new ListNode(0);
ListNode head2 = new ListNode(0);
ListNode cur1 = head1;
ListNode cur2 = head2;
ListNode cur = pHead;
while(cur != null){
if(cur.val < x){
cur1.next = cur;
cur1 = cur1.next;
}else{
cur2.next = cur;
cur2 = cur2.next;
}
cur = cur.next;
}
// 这是需要注意的地方
cur2.next = null;
cur1.next = head2.next;
return head1.next;
}6. 判断链表是否回文
chkPalindrom(ListNode A): boolean 检查链表是否回文；
reverse(ListNode head): ListNode 反转链表；
检查链表是否回文的关键首先是找到链表中点（奇数个节点找中点，偶数个节点找右中点），找到中点后从这个节点开始，逆置链表，形成两个链表；
分别从两个链表的头结点开始遍历链表，如果值不同，直接返回 false，如果值相同继续遍历，直到遍历完，返回 true；
public boolean chkPalindrome(ListNode A) {
if (A == null) return true;
ListNode fast = A;
ListNode slow = A;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode cur1 = A;
ListNode cur2 = reverse(slow);
boolean flag = true;
while (cur1.next != null && cur2.next != null) {
if (cur1.val != cur2.val) {
flag = false;
break;
}
cur1 = cur1.next;
cur2 = cur2.next;
}
return flag;
}
public ListNode reverse(ListNode head) {
ListNode newHead = new ListNode(0);
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = newHead.next;
newHead.next = cur;
cur = next;
}
return newHead.next;
}7. 找两个链表的第一个公共节点
getIntersectionNode(ListNode headA, ListNode headB): ListNode 找两个链表的第一个公共节点，没有公共节点返回 null；
定义两个指针遍历两个链表，同时让两个指针都往后走，如果相同返回节点即可；
如果不相同，当第一个指针遍历到最后，就让第一个指针指向第二个链表的头结点；同理，第二个指针边历到最后，让第二个指针也指向第一个链表；
这时候两个指针都同时向后移动，如果两个链表有公共节点，则一定会同时到达，因为两个指针速度相同，相同时间走的路程也一定相同；
如果两个链表没有公共节点，则最终会同时指向 null，返回 null 即可；
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode cur1 = headA;
ListNode cur2 = headB;
while(cur1 != cur2){
if(cur1 != null) cur1 = cur1.next;
else cur1 = headB;
if(cur2 != null) cur2 = cur2.next;
else cur2 = headA;
}
return cur1;
}8. 判断链表是否有环
hasCycle(ListNode head): boolean 判断链表是否有环；
定义一个 fast，一个 slow 指针，每次 fast 走两步，slow 每次走一步，如果两个指针相遇了，就证明有环，否则就没有环；
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
return true;
}
}
return false;
}9. 寻找链表入环的第一个节点
detectCycle(ListNode head): ListNode 寻找链表入环的第一个节点；
先找到 fast 和 slow 的相遇点，一个从起点出发，另一个从相遇点出发，最终两个指针会在环的入口点相遇；
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
break;
}
}
if(fast == null || fast.next == null) return null;
slow = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}三、模拟实现双向链表
双向链表的属性：用 head 表示链表的头节点，last 表示链表的尾巴节点；
public class MyLinkedList {
static class ListNode{
private int val;
private ListNode prev;
private ListNode next;
public ListNode(int data){
this.val = data;
}
}
public ListNode head;
public ListNode last;
}1. 遍历链表
display(): void 打印链表；
size(): int 返回链表长度；
contains(int key): boolean 判断链表中是否包含 key；
// 打印链表
public void display(){
ListNode cur = head;
while(cur != null){
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
// 返回链表长度
public int size(){
ListNode cur = head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
// 判断链表中是否包含 key
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}2. 插入节点
addFirst(int data): void 头插法，将节点插入到链表头节点的位置；
注意：如果链表没有节点，插入的时候要把头指针和尾指针都指向插入的节点；
addLast(int data): void 尾插法，将节点插入到链表尾节点的位置，尾插的时候要
注意：如果链表没有节点，插入的时候要把头指针和尾指针都指向插入的节点；
findIndexPrev(int index): ListNode 找到 index 位置节点的前驱；
addIndex(int index, int data): void 在 index 位置插入节点；
插入之前需要先判断 index 位置是否合法；
如果合法再判断一下是否是头插，是否是尾插，因为这俩方法已经写好了，可以调用；
找到要插入节点的前驱和后继，进行插入；
// 头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null) {
head = node;
last = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
// 尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null){
head = node;
last = node;
}else{
last.next = node;
node.prev = last;
last = node;
}
}
// 在 index 位置插入
public void addIndex(int index, int data){
if(index < 0 || index > size()){
throw new RuntimeException(index + "位置不合法！");
}
if(index == 0){
addFirst(data);
return;
}else if(index == size()){
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode prevNode = findPrev(index);
ListNode nextNode = prevNode.next;
prevNode.next = node;
node.prev = prevNode;
node.next = nextNode;
nextNode.prev = node;
}
private ListNode findPrev(int index){
ListNode cur = head;
while(--index > 0){
cur = cur.next;
}
return cur;
}3. 删除节点
remove(int key): void 删除第一个值为 key 的节点；
找到要删除节点的前驱和后继；
如果前驱为空，就删除头节点，删除头结点要特殊处理只有一个节点的情况；
如果后继为空，就删除尾节点，删除尾节点要特殊处理只有一个节点的情况；
如果删除中间节点，删除后返回；
removeAll(int key): void 删除所有值为 key 的节点；
注意：原理同上，不同点是删除一个节点后，继续向后遍历；
// 删除第一次出现关键字 key 的节点
public void remove(int key){
ListNode cur = head;
while(cur != null){
if(cur.val == key){
ListNode prevNode = cur.prev;
ListNode nextNode = cur.next;
if(prevNode != null) {
prevNode.next = nextNode;
}else{
head = head.next;
if(head != null){
head.prev = null;
}
}
if(nextNode != null) {
nextNode.prev = prevNode;
}else{
last = last.prev;
if(last != null){
last.next = null;
}
}
break;
}
cur = cur.next;
}
}
// 删除所有值为 key 的节点
public void removeAll(int key){
ListNode cur = head;
while(cur != null) {
if (cur.val == key) {
ListNode prevNode = cur.prev;
ListNode nextNode = cur.next;
if (prevNode != null) {
prevNode.next = nextNode;
} else {
head = head.next;
if(head != null){
head.prev = null;
}
}
if (nextNode != null) {
nextNode.prev = prevNode;
} else {
last = last.prev;
if(last != null){
last.next = null;
}
}
cur = nextNode;
}else{
cur = cur.next;
}
}
}4. 清空链表
clear(): void 清空链表；
注意：要把 head 和 last 置空；
public void clear(){
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur = null;
cur = next;
}
head = null;
last = null;
}四、ArrayList 和 LinkedList 的区别
存储上：
ArrayList 在存储空间上是连续的，LinkedList 逻辑上是，连续的，在存储空间上是不一定连续的；
操作上：
从查询元素上来说，ArrayList 的时间复杂度是 O(1)，而 LinkedList 不支持随机访问；
从插入上来说：
LinkedList 的时间复杂度是 O(1)，ArrayList 头插时间复杂度是 O(n)，因为需要把把元素统一往后移一个位置；
ArrayList 在插入时，空间不够时，需要扩容，而 LInkedList 没有容量的概念；
应用场景：
ArrayList 适合频繁查询，LinkedList 适合频繁插入删除；