单链表（Linked List）

定义一个接口List类 public interface List<E> { static final int ELEMENT_NOT_FOUND = -1; /* 清除所有元素 */ void clear(); /* 元素的数量 */ int size(); /* 是否为空 */ boolean isEmpty(); /** * 是否包含某个元素 * @param element * @return */ boolean contains(E element); /** * 添加元素到尾部 * @param element */ void add(E element); /** * 获取index位置的元素 * @param index * @return */ E get(int index); /** * 设置index位置的元素 * @param index * @param element * @return 原来的元素ֵ */ E set(int index, E element); /** * 在index位置插入一个元素 * @param index * @param element */ void add(int index, E element); /** * 删除index位置的元素 * @param index * @return */ E remove(int index); /** * 查看元素的索引 * @param element * @return */ int indexOf(E element); } 定义一个AbstractList类继承List接口 public abstract class AbstractList<E> implements List<E> { /* 元素的数量 */ protected int size; /* 元素的数量 */ public int size() { return size; } /* 是否为空 */ public boolean isEmpty() { return size == 0; } /** * 是否包含某个元素 * @param element * @return */ public boolean contains(E element) { return indexOf(element) != ELEMENT_NOT_FOUND; } /* 添加元素到尾部 */ public void add(E element) { add(size, element); } protected void outOfBounds(int index) { throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); } protected void rangeCheck(int index) { if (index < 0 || index >= size) { outOfBounds(index); } } protected void rangeCheckForAdd(int index) { if (index < 0 || index > size) { outOfBounds(index); } } } 动态数组有个明显的缺点：可能会造成内存空间的大量浪费而对于链表来说可以解决这个缺点链表：是一种链式存储的线性表，所有元素的内存地址不一定是连续的

链表的设计

public class LinkedList<E> extends AbstractList<E>{ private Node<E> first; private static class Node<E> { E element; Node<E> next; public Node(E element, Node<E> next) { this.element = element; this.next = next; } } } 链表的大部分接口和动态数组是一致的；两者都继承List接口。

（1）清空元素 - clear()

LinkedList底层封装clear元素清空 @Override public void clear() { size = 0; first = null; }

因为只需要将first赋值为null，那么就无法指向下一个第一个元素的element，也就无法调取后面的数值；相当于将LinkedList清空。

LinkedList底层封装获取index位置对应节点对象 /** * 获取index位置对应节点对象 * @param index * @return */ private Node<E> node(int index){ rangeCheck(index); Node<E> node = first; for (int i = 0; i < index; i++) { node = node.next; } return node; } protected void rangeCheck(int index) { if (index<0 || index>=size) { outBounds(index); } }

（2）set、get节点元素

LinkedList底层封装获取节点元素和设置节点元素的值 @Override public E get(int index) { return node(index).element; } @Override public E set(int index, E element) { Node<E> node = node(index); E old = node.element; node.element = element; return old; }

get：通过node(index)方法来获取对应节点对象中的值。

set：通过Node<E> node = node(index);来获取index对应节点对象；然后通过node.element来获取节点的值，通过交换的方式给index位置上赋值新的数值。

LinkedList底层封装添加元素- add()

@Override public void add(int index, E element) { /* * 最好：O(1) * 最坏：O(n) * 平均：O(n) */ rangeCheckForAdd(index); if (index == 0) { first = new Node<>(element, first); } else { Node<E> prev = node(index - 1); prev.next = new Node<>(element, prev.next); } size++; } protected void rangeCheckForAdd(int index) { if (index < 0 || index > size) { outBounds(index); } } LinkedList底层封装删除元素- remove() @Override public E remove(int index) { /* * 最好：O(1) * 最坏：O(n) * 平均：O(n) */ rangeCheck(index); Node<E> node = 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; } protected void rangeCheck(int index) { if (index<0 || index>=size) { outBounds(index); } } LinkedList底层封装查看元素的位置- indexOf() /* 查看元素的位置 */ @Override 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 -1; } LinkedList底层封装toString方法 public String toString() { StringBuilder string = new StringBuilder(); string.append("size=").append(size).append(", ["); Node<E> node = first; for (int i = 0; i < size; i++) { if (i != 0) { string.append(", "); } string.append(node.element); node = node.next; } string.append("]"); return string.toString(); }

练习题1—删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。 现有一个链表 – head = [4,5,1,9]，它可以表示为: 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list 输入：head = [4,5,1,9], node = 1 输出：[4,5,9] 解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

提示： ①、链表至少包含两个节点。 ②、链表中所有节点的值都是唯一的。 ③、给定的节点为非末尾节点并且一定是链表中的一个有效节点。 ④、不要从你的函数中返回任何结果。

public class Main { class ListNode { int val;//存放数据 ListNode next;//用来指向下一个节点 ListNode(int x) { val = x; } } class Solution { public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } } }

解题思路：先找到我们需要删除的节点A，然后找到我们需要删除的节点A的下一个节点B的数值覆盖掉我们要删除的节点A的数值node.val = node.next.val;；覆盖之后，我们需要将删除的节点A的next指向next的next（相当于我们将B节点的数值覆盖掉A节点的值后，A节点的next指向B节点后面C节点）

练习2—反转链表

反转一个单链表。（面试题） 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list

方法一：递归

class ListNode { int val;//存放数据 ListNode next;//用来指向下一个节点 ListNode(int x) { val = x; } } class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; } } 方法二：迭代 class ListNode { int val;//存放数据 ListNode next;//用来指向下一个节点 ListNode(int x) { val = x; } } class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = null; while (head != null) { ListNode tmp = head.next; head.next = newHead; newHead = head; head = tmp; } return newHead; } }

练习3—环形链表

给定一个链表，判断链表中是否有环。

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-cycle

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1 输出：false 解释：链表中没有环。

class ListNode { int val;//存放数据 ListNode next;//用来指向下一个节点 ListNode(int x) { val = x; } } class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) return false; ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; } }