一、链表的基础概念

用于解决 ArrayList 中，插入、删除时间复杂度较大，且可能会浪费空间的问题

1.1 什么是链表

逻辑上是连续的，物理上(内存上)是不连续的，由一个个节点组成

1.2 分类

• 单向 / 双向
  

• 带头的 / 不带头的
  

• 循环 / 非循环
  

1.3 链表的底层代码

public class MyStringList {private ListNode head;class ListNode{private int val;private ListNode next;public ListNode(int val) {this.val = val;}}public void creatList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(24);ListNode node3 = new ListNode(36);ListNode node4 = new ListNode(48);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = null;head = node1;}//打印这个链表的所有元素public void display() {ListNode cur = head;while (cur != null){System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}//得到单链表的长度public int size(){int count = 0;ListNode cur = head;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;}//头插法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);if (head == null){head = node;return;}ListNode cur = head;while (cur.next != null){cur = cur.next;}cur.next = node;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){ListNode cur = head;ListNode node = new ListNode(data);if (!checkIndex(index)){throw new IndexException("下标输入错误 " + index);}if (index == 0){addFirst(data);return;}if (index == this.size()){addLast(data);}//找到for (int i = 0; i < index - 1; i++) {cur = cur.next;}//交换node.next = cur.next;cur.next = node;}private boolean checkIndex(int index){if (index < 0 || index > this.size() ){return false;}return true;}//删除第一次出现关键字为key的节点public void remove(int key){if (head == null){return;}if (head.val == key){head = head.next;return;}ListNode prev = searchPrev(key);if (prev == null){System.out.println("没有这个数据");return;}ListNode del = prev.next;prev.next = del.next;}private ListNode searchPrev(int key){ListNode prev = head;while (prev.next != null){if (prev.next.val == key){return prev;}else{prev = prev.next;}}return null;}//删除所有值为key的节点public void removeAllKey(int key){if (head == null){return;}while (head.val == key){head = head.next;}ListNode cur = head.next;ListNode prev = head;while (cur != null){if (cur.val == key){prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}}public void clear() {//this.head = null;   第一种方法while (head != null) {ListNode headNext = head.next;   //第二种方法head.next = null;head = headNext;}}
}

1.4 例题

一、移除链表元素

class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null){return head;}ListNode cur = head.next;ListNode pre = head;while (cur != null){if (cur.val == val){cur = cur.next;pre.next = cur;}else{pre = cur;cur = cur.next;}}if (head.val == val){head = head.next;}return head;}
}

二、反转一个单链表

class Solution {public ListNode reverseList(ListNode head) {if (head == null){return null;}if (head.next == null){return head;}ListNode cur = head.next;head.next = null;while (cur != null){ListNode curNext = cur.next;cur.next = head;head = cur;cur = curNext;}return head;}
}

三、链表的中间节点

class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null){fast= fast.next.next;slow = slow.next;}return slow;}
}

四、链表中倒数第四个节点

public ListNode FindKthToTail(ListNode head,int k) {ListNode fast = head;ListNode slow = head;if (head == null || k <= 0){return null;}for(int i = 0; i < k - 1; i++){fast = fast.next;if (fast == null){return null;}}while (fast.next != null){slow = slow.next;fast = fast.next;}return slow;
}

五、合并两个有序链表

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newHead = new ListNode();ListNode tmpH = newHead;while (list1 != null && list2 != null){if (list1.val < list2.val){tmpH.next = list1;tmpH = tmpH.next;list1 = list1.next;}else {tmpH.next = list2;tmpH = tmpH.next;list2 = list2.next;}}if (list1 != null){tmpH.next = list1;}else {tmpH.next = list2;}return newHead.next;}
}

六、链表分割

public class Partition {public ListNode partition(ListNode pHead, int x) {ListNode ae = null;ListNode as = null;ListNode be = null;ListNode bs = null;while (pHead != null){if (pHead.val < x){if (ae == null){ae = pHead;as = pHead;}else{as.next = pHead;as = as.next;}}else{if (be == null){be = pHead;bs = pHead;}else {bs.next = pHead;bs = bs.next;}}pHead = pHead.next;}if (ae == null){return be;}as.next = be;if (be != null){bs.next = null;}return ae;}
}

七、链表的回文结构

public class PalindromeList {public boolean chkPalindrome(ListNode A) {ListNode slow = A;ListNode fast = A;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}//翻转ListNode cur = slow.next;while (cur != null){ListNode curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;}//判断while (A != slow){if (A.val != slow.val){return false;}if (A.next == slow){return true;}A = A.next;slow = slow.next;}return true;}
}

八、相交链表

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode plong = headA;ListNode pshort = headB;//1、分别求两个链表的长度int len1 = 0;int len2 = 0;//O(M)while (plong != null) {len1++;plong = plong.next;}//O(N)while (pshort != null) {len2++;pshort = pshort.next;}plong = headA;pshort = headB;//2、求差值步的lenint len = len1 - len2;if(len < 0) {plong = headB;pshort = headA;len = len2 - len1;}//3、哪个链表长 走len步while (len != 0) {plong = plong.next;len--;}//4、一起走 直到相遇！while (plong != pshort) {plong = plong.next;pshort = pshort.next;}return plong;}

九、环形列表

public class Solution {public boolean hasCycle(ListNode head) {if (head == null){return false;}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;}
}

十、环形列表||

public class Solution {public ListNode detectCycle(ListNode head) {if (head == null){return null;}ListNode slow = head;ListNode fast = 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;}fast = head;while (fast != slow){fast = fast.next;slow = slow.next;}return fast;}
}

1.5 LinkedList 的实现

（1）什么是LInkedList

（2）底层代码

public class MyLinkedList {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//得到链表的长度   和双向 没有关系 ！！！public int size(){int len = 0;ListNode cur = head;while (cur != null) {cur = cur.next;len++;}return len;}public void display(){ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}//查找是否包含关键字key是否在链表当中public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//头插法public void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {head = node;last = node;         //第一种写法return;}node.next = head;head.prev = node;head = node;/*if(head == null) {head = 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;//last = last.next;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){int size = size();if(index < 0 || index > size) {throw new IndexOutOfBounds("双向链表index不合法！");}if(index == 0) {addFirst(data);return;}if(index == size) {addLast(data);return;}ListNode cur = head;while (index != 0) {cur = cur.next;index--;}ListNode node = new ListNode(data);node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {//开始删if(cur == head) {//删除头节点head = head.next;//只要1个节点的时候if(head != null) {head.prev = null;}else {last = null;}}else {cur.prev.next = cur.next;if(cur.next != null) {//cur.prev.next = cur.next;cur.next.prev = cur.prev;}else {//cur.prev.next = cur.next;last = last.prev;}}return;}else {cur = cur.next;}}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {//开始删if (cur == head) {//删除头节点head = head.next;//只要1个节点的时候if (head != null) {head.prev = null;}else {last = null;}} else {cur.prev.next = cur.next;if (cur.next != null) {//cur.prev.next = cur.next;cur.next.prev = cur.prev;} else {//cur.prev.next = cur.next;last = last.prev;}}}cur = cur.next;}}public void clear(){ListNode cur = head;while (cur != null) {ListNode curNext = cur.next;cur.prev = null;cur.next = null;//cur.val = null;     如果cur.val是引用的情况cur = curNext;}head = null;last = null;}
}

（3）LinkedLIst的使用

❤️构造

List<Integer> list1 = new LinkedList<>();
List<String> list2 = new LinkedList<>();
List<String> list3 = new LinkedList<>(list2);

❤️方法

❤️遍历

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());//直接打印System.out.println(linkedList);// foreach遍历for (int e:list) {System.out.print(e + " ");}System.out.println();// 使用迭代器遍历---正向遍历ListIterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next()+ " ");}System.out.println();// 使用反向迭代器---反向遍历ListIterator<Integer> rit = list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() +" ");}System.out.println();
}

1.6 ArrayList和LinkedList的区别