链表知识回首

范例：单链表，双链表、循环链表

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

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

添加节点： 

链表的构造函数

1. public class ListNode {
2.     // 结点的值
3.     int val;
4.     // 下一个结点
5.     ListNode next;
6.     // 节点的构造函数(无参)
7.     public ListNode() {
8.     }
9.     // 节点的构造函数(有一个参数)
10.     public ListNode(int val) {
11.         this.val = val;
12.     }
13.     // 节点的构造函数(有两个参数)
14.     public ListNode(int val, ListNode next) {
15.         this.val = val;
16.         this.next = next;
17.     }
18. }

复制代码

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

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

复制代码

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

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

1. LinkedList<Integer> list = new LinkedList<Integer>();
2. List<Integer> list1 =new LinkedList<Integer>();
3. List<Integer> list2 =new ArrayList<>();
4. LinkedList list3 = new LinkedList();

复制代码

 上述是常见的链表的声明方式
第一种，变量的声明范例和现实实现范例都是LinkedList，可直接调用 LinkedList 类中特有的方法，而且声明白泛型Integer，确保只能存储 Integer 范例的数据，编译期间就能举行范例检查，避免了范例转换非常。
第二种，声明范例是接口 List范例，现实实现的范例确实LinkedList，但只能调用 List 接口中定义的方法。如果必要使用 LinkedList 特有的方法（如队列或双端队列相关的方法），则必要显式地举行范例转换。同样使用了泛型 <Integer>，确保范例安全。
第三种声明范例是接口List，实现的是ArrayList范例，ArrayList 支持快速随机访问，时间复杂度为 O(1)。在数组中心插入或删除元素时必要移动元素，时间复杂度为 O(n)；而 LinkedList 在任意位置添加或删除（假如已经有相应节点引用）通常更高效。
第四种实现的是原始范例（由于没有使用泛型），编译器不会对聚会合的数据举行范例检查，
手搓链表

1. public class Linked {
2.     static class Node{
3.         int data;
4.         Node next;
5.         public Node(){};
6.         public Node(int data){
7.             this.data = data;
8.             this.next =null;
9.         }
10.     }
11.     public static class SingleLinkedList{
12.         private Node head;
13.         public void addFirst(int data){
14.             Node newNode = new Node(data);
15.             newNode.next = head;
16.             head = newNode;
17.         }
19.         public void addLast(int data){
20.             Node newNode = new Node(data);
21.             if(head ==null){
22.                 head = newNode;
23.                 return;
24.             }
25.             Node curr = head;
26.             while(curr.next != null){
27.                 curr = curr.next;
28.             }
30.             curr.next = newNode;
31.         }
32.         public boolean remove(int data){
33.             if(head == null){//若链表为空，则删除失败
34.                 return false;
35.             }
36.             if(head.data == data){//还要先判断头节点是否时要删除的
37.                 head = head.next;
38.                 return true;
39.             }
40.             Node curr = head;
41.             while(curr.next != null && curr.next.data != data){
42.                 curr = curr.next;
43.             }
44.             if (curr.next != null) {
45.                 curr.next = curr.next.next;
46.                 return true;
47.             }
48.             return false;
49.         }
50.         public void printList() {
51.             Node curr = head;
52.             while (curr != null) {
53.                 System.out.print(curr.data + " ");
54.                 curr = curr.next;
55.             }
56.             System.out.println("null");
57.         }
58.     }
59.     public static void main(String[] args) {
60.         SingleLinkedList list = new SingleLinkedList();
61.         list.addFirst(4);
62.         list.addFirst(3);
63.         list.addFirst(2);
64.         list.addFirst(1);
65.         list.addLast(5);
66.         list.addLast(6);
67.         list.printList();//1 2 3 4 5 6 null
68.         list.remove(6);
69.         list.printList();//1 2 3 4 5 null
70.     }
71. }

复制代码

反转链表

题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL，即右移

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode reverseList(ListNode head) {
13.         // 如果链表为空，则直接返回null
14.         if(head == null){
15.             return null;
16.         }
17.         
18.         // prev指针初始化为null，最后会成为反转后链表的头节点
19.         ListNode prev = null;
20.         // cur指针指向当前要处理的节点，开始时指向链表头head
21.         ListNode cur = head;
22.         // temp用于保存当前节点cur的下一个节点，防止在改变指针关系后丢失引用
23.         ListNode temp = null;
24.         
25.         // 当当前节点不为空时，循环执行反转操作
26.         while (cur != null) {
27.             // 保存cur的下一个节点，防止链表断裂
28.             temp = cur.next; // 此时temp指向cur的下一节点
29.             
30.             // 将当前节点的next指针指向前一个节点，实现局部反转
31.             cur.next = prev; // 当前节点的next由原来的下一个节点变为前一个节点
32.             
33.             // 将prev移动到当前节点位置，为下一次反转操作做准备
34.             prev = cur;
35.             
36.             // 将cur后移到下一个节点，也就是之前保存的temp
37.             cur = temp;
38.         }
39.         
40.         // 循环结束后，prev指向反转后的链表头节点，返回它作为新的链表起点
41.         return prev;
42.     }
43. }

复制代码

链表内两两交换

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改背叛点内部的值，而是必要现实的举行节点交换。
解1：

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

1. public class Solution {
2.     public ListNode swapPairs(ListNode head) {
3.         // 创建哑结点，它的 next 指向原链表的头
4.         ListNode dummy = new ListNode(0);
5.         dummy.next = head;
6.         ListNode current = dummy;
7.         
8.         // 循环条件：当前结点后面至少有两个节点
9.         while (current.next != null && current.next.next != null) {
10.             // 定义要交换的两个节点
11.             ListNode first = current.next;
12.             ListNode second = current.next.next;
13.             
14.             // 交换节点：
15.             // 1. 先将 first 指向 second 的下一个节点
16.             first.next = second.next;
17.             // 2. second 指向 first
18.             second.next = first;
19.             // 3. current 指向 second，完成与前面的连接
20.             current.next = second;
21.             
22.             // 移动 current，跳过刚才交换的两个节点
23.             current = first;
24.         }
25.         
26.         // 返回哑结点的 next，即新的头节点
27.         return dummy.next;
28.     }
29. }

复制代码

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

1. import java.util.ArrayList;
2. import java.util.List;
4. public class Solution {
5.     public ListNode swapPairs(ListNode head) {
6.         if (head == null || head.next == null) {
7.             return head;
8.         }
10.         // 1. 将链表节点存入数组
11.         List<ListNode> nodes = new ArrayList<>();
12.         ListNode current = head;
13.         while (current != null) {
14.             nodes.add(current);
15.             current = current.next;
16.         }
18.         // 2. 在数组中交换相邻节点
19.         for (int i = 0; i < nodes.size() - 1; i += 2) {
20.             // 交换nodes[i]与nodes[i+1]
21.             ListNode temp = nodes.get(i);
22.             nodes.set(i, nodes.get(i+1));
23.             nodes.set(i+1, temp);
24.         }
26.         // 3. 重建链表（根据交换后的数组重设每个节点的next指针）
27.         for (int i = 0; i < nodes.size() - 1; i++) {
28.             nodes.get(i).next = nodes.get(i + 1);
29.         }
30.         // 最后一个节点的next设为null
31.         nodes.get(nodes.size() - 1).next = null;
33.         // 4. 返回新的链表头（数组中第一个元素）
34.         return nodes.get(0);
35.     }
36. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。