链表知识回顾

类型：单链表，双链表、循环链表

存储：在内存中不是连续存储

删除操作：即让c的指针指向e即可，无需释放d，因为java中又内存回收机制

添加节点： 

链表的构造函数

public class ListNode {// 结点的值int val;// 下一个结点ListNode next;// 节点的构造函数(无参)public ListNode() {}// 节点的构造函数(有一个参数)public ListNode(int val) {this.val = val;}// 节点的构造函数(有两个参数)public ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

可以直接用java自带的LinkedList类实现链表的初始化

import java.util.LinkedList;public class Main {public static void main(String[] args) {// 创建一个空的链表LinkedList<Integer> list = new LinkedList<>();// 向链表中添加元素list.add(1);list.add(2);list.add(3);// 打印链表内容System.out.println(list);}
}

链表的声明：

Java标准库提供了LinkedList类，位于java.util包中。它的特点如下：

• 实现细节：LinkedList底层通常实现为双向链表，这意味着每个节点除了指向下一个节点，还保存对前一个节点的引用。
• 接口实现：除了实现List接口外，LinkedList还实现了Deque接口，使其既可以当作列表使用，也可以当作队列（或双端队列）使用。
• 增删操作：add(), remove(), offer(), poll()等方法在链表头尾插入或删除元素时性能较高。
• 遍历操作：由于链表没有下标索引，随机访问通常较慢。如果频繁使用随机访问，可以考虑使用ArrayList，ArrayList 底层是基于动态数组实现的

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

 上述是常见的链表的声明方式

第一种，变量的声明类型和实际实现类型都是LinkedList，可直接调用 LinkedList 类中特有的方法，并且声明了泛型Integer，确保只能存储 Integer 类型的数据，编译期间就能进行类型检查，避免了类型转换异常。

第二种，声明类型是接口 List类型，实际实现的类型确实LinkedList，但只能调用 List 接口中定义的方法。如果需要使用 LinkedList 特有的方法（如队列或双端队列相关的方法），则需要显式地进行类型转换。同样使用了泛型 <Integer>，确保类型安全。

第三种声明类型是接口List，实现的是ArrayList类型，ArrayList 支持快速随机访问，时间复杂度为 O(1)。在数组中间插入或删除元素时需要移动元素，时间复杂度为 O(n)；而 LinkedList 在任意位置添加或删除（假如已经有相应节点引用）通常更高效。

第四种实现的是原始类型（因为没有使用泛型），编译器不会对集合中的数据进行类型检查，

手搓链表

public class Linked {static class Node{int data;Node next;public Node(){};public Node(int data){this.data = data;this.next =null;}}public static class SingleLinkedList{private Node head;public void addFirst(int data){Node newNode = new Node(data);newNode.next = head;head = newNode;}public void addLast(int data){Node newNode = new Node(data);if(head ==null){head = newNode;return;}Node curr = head;while(curr.next != null){curr = curr.next;}curr.next = newNode;}public boolean remove(int data){if(head == null){//若链表为空，则删除失败return false;}if(head.data == data){//还要先判断头节点是否时要删除的head = head.next;return true;}Node curr = head;while(curr.next != null && curr.next.data != data){curr = curr.next;}if (curr.next != null) {curr.next = curr.next.next;return true;}return false;}public void printList() {Node curr = head;while (curr != null) {System.out.print(curr.data + " ");curr = curr.next;}System.out.println("null");}}public static void main(String[] args) {SingleLinkedList list = new SingleLinkedList();list.addFirst(4);list.addFirst(3);list.addFirst(2);list.addFirst(1);list.addLast(5);list.addLast(6);list.printList();//1 2 3 4 5 6 nulllist.remove(6);list.printList();//1 2 3 4 5 null}
}

反转链表

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL，即右移

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {// 如果链表为空，则直接返回nullif(head == null){return null;}// prev指针初始化为null，最后会成为反转后链表的头节点ListNode prev = null;// cur指针指向当前要处理的节点，开始时指向链表头headListNode cur = head;// temp用于保存当前节点cur的下一个节点，防止在改变指针关系后丢失引用ListNode temp = null;// 当当前节点不为空时，循环执行反转操作while (cur != null) {// 保存cur的下一个节点，防止链表断裂temp = cur.next; // 此时temp指向cur的下一节点// 将当前节点的next指针指向前一个节点，实现局部反转cur.next = prev; // 当前节点的next由原来的下一个节点变为前一个节点// 将prev移动到当前节点位置，为下一次反转操作做准备prev = cur;// 将cur后移到下一个节点，也就是之前保存的tempcur = temp;}// 循环结束后，prev指向反转后的链表头节点，返回它作为新的链表起点return prev;}
}

链表内两两交换

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解1：

• 创建一个虚拟头节点dummy指向head，定义current指针真相虚拟头节点
• 进入循环体内，确定current每次后面都能有两个节点进行交换操作
• 定义first和second分别指向第一个节点和第二个节点，
• 然后让第二个节点指向第一个节点，第一个节点指向下一个要交换的第一个节点，最后让current指向交换后的第一个节点
• 2，3，4循环操作，直至不够节点互换退出循环，返回虚拟头节点之后的head

public class Solution {public ListNode swapPairs(ListNode head) {// 创建哑结点，它的 next 指向原链表的头ListNode dummy = new ListNode(0);dummy.next = head;ListNode current = dummy;// 循环条件：当前结点后面至少有两个节点while (current.next != null && current.next.next != null) {// 定义要交换的两个节点ListNode first = current.next;ListNode second = current.next.next;// 交换节点：// 1. 先将 first 指向 second 的下一个节点first.next = second.next;// 2. second 指向 firstsecond.next = first;// 3. current 指向 second，完成与前面的连接current.next = second;// 移动 current，跳过刚才交换的两个节点current = first;}// 返回哑结点的 next，即新的头节点return dummy.next;}
}

解2：将链表转换为队列处理，在重建链表

import java.util.ArrayList;
import java.util.List;public class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}// 1. 将链表节点存入数组List<ListNode> nodes = new ArrayList<>();ListNode current = head;while (current != null) {nodes.add(current);current = current.next;}// 2. 在数组中交换相邻节点for (int i = 0; i < nodes.size() - 1; i += 2) {// 交换nodes[i]与nodes[i+1]ListNode temp = nodes.get(i);nodes.set(i, nodes.get(i+1));nodes.set(i+1, temp);}// 3. 重建链表（根据交换后的数组重设每个节点的next指针）for (int i = 0; i < nodes.size() - 1; i++) {nodes.get(i).next = nodes.get(i + 1);}// 最后一个节点的next设为nullnodes.get(nodes.size() - 1).next = null;// 4. 返回新的链表头（数组中第一个元素）return nodes.get(0);}
}

删除链表中倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解1：首先找到长度，然后循环遍历找到那个结点的位置在删除，但过程中没有考虑到如果删除到头节点的情况

public ListNode removeNthFromEnd(ListNode head, int n) {// 1) 先算长度int len = 0;for (ListNode cur = head; cur != null; cur = cur.next) {len++;}// 2) n == len，删头if (n == len) {return head.next;}// 3) 找到第 (len - n) 个节点，它的 next 就是要删的ListNode cur = head;for (int i = 1; i < len - n; i++) {cur = cur.next;}// 4) 删除cur.next = cur.next.next;return head;
}

解2：利用虚拟头节点，和快慢指针，快指针先走n步，然后快慢指针一块走直至快指针走到头，这是慢指针指向待删除节点的前一个节点。创建虚拟头节点时，记得让虚拟头节点指向head

为什么尽量推荐使用虚拟头节点，因为可以避免头节点被删除或者更换情况。

设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1);dummy.next = head;ListNode first =dummy;ListNode slow = dummy;for(int i=0;i<n;i++) {first = first.next;}while(first.next != null){first = first.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;
}
}

链表相交 

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

思想：这里并不是简单的找到数值相等的节点，而是找到指针相等的节点，所以大概步骤就是；找到AB链表的长度，先让A指针走到和B链表长度一样的地方一起走，若有相同的节点，则返回值

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA=0,lenB=0;for (ListNode cur = headA; cur != null; cur = cur.next) {lenA++;}for (ListNode cur = headB; cur != null; cur = cur.next) {lenB++;}ListNode A = (lenA >= lenB) ? headA : headB;ListNode B = (lenA >= lenB) ? headB : headA;int gap = Math.abs(lenA - lenB);while(gap > 0){A = A.next;gap --;}while(A != null && B != null){if(A == B) return A;A = A.next;B = B.next;}return null;}
}

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

思想：利用快慢指针，让快指针一次走两个，慢指针一次走一个，若有环则一定会相交。

public class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head;// 注意这里用 &&，两者都非 null 时才能继续下走while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {return true;}}return false;}
}

环形链表2

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

思想：首先，利用快慢指针判断是否有环，并且在快慢指针相等的地方做标记，

最重要的是如何找到环的入口，在定义指向头结点的指针和指向快慢相等结点的指针，两个指针同时向前走，当相遇时即是环的入口。

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 有环ListNode index1 = fast;ListNode index2 = head;// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口while (index1 != index2) {index1 = index1.next;index2 = index2.next;}return index1;}}return null;}
}