1. 含义
链表 是一种 链式存储 的线性表，所有元素的内存地址不一定是连续的
2. 基本方法
1. size() : int //返回链表长度
2. isEmpty() : boolean // 判空
3. clear() : void //清除所有元素
4. contains(E element) : boolean //判断是否包含此元素
5. get(int index) : E //返回该下标处的元素
6. set(int index, E) : E //修改该下标处的元素
7. add(E element) : void //末尾添加元素
8. add(int index, E) : void //指定下标处添加元素
9. remove(int index) : E //移除指定下标处的元素
10. indexof(E element) : int //返回该元素的下标
3. 内部实现
1. Node节点设计
private static class Node<E> {
// 存储元素
E element;
// 存储下一个节点
Node<E> next;
// 构造方法
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}2. 方法设计
1. size()
public int size() {
return size;
}2. isEmpty()
public boolean isEmpty() {
return size == 0;
}3. clear()
public void clear() {
size = 0;
first = null;
}4. contains(E element)
public boolean contains(E element) {
// 返回下标如果不为常数-1则存在，反之不存在
return indexOf(element) != ELEMENT_NOT_FOUND;
}5. get(int index)
public E get(int index) {
return node(index).element;
}
// 用于获取index位置对应的节点对象
private Node<E> node(int index) {
// 判断下标是否越界
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}6. set(int index, E)
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}7. add(E element)
public void add(E element) {
add(size, element);
}8. add(int index, E)
public void add(int index, E element) {
// 判断下标是否越界
rangeCheckForAdd(index);
if (index == size) { // 往最后面添加元素
Node<E> next = node(index);
last = new Node<>(element, next);
if (oldLast == null) { // 这是链表添加的第一个元素
first = last;
} else {
oldLast.next = last;
}
} else {
Node<E> prev = node(index - 1);
Node<E> next = node(index);
Node<E> node = new Node<>(element, next);
if (prev == null) { // index == 0
first = node;
} else {
prev.next = node;
}
}
size++;
}9. remove(int index)
public E remove(int index) {
rangeCheck(index);
Node<E> node = first;
// 将first指向下一个节点
if(index == 0){
first = first.next;
} else {
// 获取前一个节点
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}10. indexof(E element)
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}4. 练习题目
237. 删除链表中的节点 - 力扣（LeetCode）
有一个单链表的
head，我们想删除它其中的一个节点node。给你一个需要删除的节点
node。你将 无法访问 第一个节点head。链表的所有值都是 唯一的，并且保证给定的节点
node不是链表中的最后一个节点。删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
node前面的所有值顺序相同。node后面的所有值顺序相同。示例 1：
输入：head = [4,5,1,9], node = 5 输出：[4,1,9] 解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9示例 2：
输入：head = [4,5,1,9], node = 1 输出：[4,5,9] 解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9
分析
因为链表的所有值都是 唯一的，并且保证给定的节点
node不是链表中的最后一个节点。只需删除给定的节点，所以可以巧妙利用下一个值来覆盖要删除的节点，并把删除节点指向下个节点的下个节点，从而达到删除此节点的效果。
题解
class Solution {
public void deleteNode(ListNode node) {
// 让下一个节点的值覆盖掉要删除节点的值
node.val = node.next.val;
// 让要删除的节点指向下个节点个下个节点
node.next = node.next.next;
}
}206. 反转链表 - 力扣（LeetCode）
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：
输入：head = [1,2] 输出：[2,1]示例 3：
输入：head = [] 输出：[]
分析
方法一：迭代法
一直循环到head为空则结束
方法二：递归法
reverseList(head.next)实现了将后面节点反转的功能，再将head的下一个节点的下一个节点指向头节点head，最后将head节点的next指向空，实现反转。
题解
方法一：迭代法
class Solution {
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
while(head != null){
// 临时节点指向下一个节点
ListNode temp = head.next;
// 将头节点的next指向新节点
head.next = newHead;
// 将新节点指向头节点
newHead = head;
// 最后将头节点指向临时节点
// 实现了从头挨个把头节点拿出来放在新节点最后的翻转效果
head = temp;
}
return newHead;
}
}方法二：递归法
class Solution {
public ListNode reverseList(ListNode head) {
// 头节点为空或头节点的下一个指向为空，直接返回
if(head == null || head.next == null) return head;
else{
// 将head后面的链表用递归法实现反转
ListNode newHead = reverseList(head.next);
// 将倒数第二个节点指向头节点
head.next.next = head;
// 将头节点的next指向空
head.next = null;
return newHead;
}
}
}141. 环形链表 - 力扣（LeetCode）
给你一个链表的头节点
head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回
true。 否则，返回false。示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
分析
利用快慢指针，两指针初始位置不同，移动距离不同，如果快指针和慢指针相遇，则有环，如果快指针走到最后都没有相遇，则无环。
题解
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
// 定义快慢指针，初始位置不同
ListNode slow = head;
ListNode fast = head.next;
// fast不为空且下一个不为空时循环
while(fast != null && fast.next != null){
// 快慢指针相遇
if(slow == fast) return true;
// 慢走一，快走二
slow = slow.next;
fast = fast.next.next;
}
return false;
}
}标签：node,head,Java,next,链表,element,节点 From： https://blog.csdn.net/2301_80395772/article/details/140855597