一、什么是链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
二、链表的分类
2.1 单链表
2.2 双链表
2.3 循环链表
三、代码实现（双链表）
/** * @author 17122 */ public class MyLinkedList<E> implements Iterable<E> { private int size; /** * 改变次数 */ private int modCount = 0; /** * 头结点指针 指向上一个Node的值 */ private Node<E> beginMarker; /** * 尾结点指针 指向下一个Node的值 */ private Node<E> endMarker; /** * 静态内部类 * * @param <E> */ private static class Node<E> { public E data; //值 public Node<E> prev; //上一个元素值 public Node<E> next; //下一个元素值 public Node(E data, Node<E> prev, Node<E> next) { this.data = data; this.prev = prev; this.next = next; } } /** * 空构造 */ public MyLinkedList() { doClear(); } /** * 清空数组 */ private void doClear() { beginMarker = new Node<E>(null, null, null); endMarker = new Node<E>(null, beginMarker, null); beginMarker.next = endMarker; size = 0; modCount++; } /** * 返回大小 * * @return */ private int size() { return size; } /** * 判断是否为空 * * @return */ public boolean isEmpty() { return size == 0; } /** * 添加一个元素 * * @param item */ public void add(E item) { add(size(), item); } /** * 向一个位置添加元素 * * @param index * @param item */ public void add(int index, E item) { addBefore(getNode(index, 0, size), item); } /** * 获取一个元素 * * @param index * @return */ public E get(int index) { return getNode(index).data; } /** * 获取一个节点 * * @param index * @return */ private Node<E> getNode(int index) { return getNode(index, 0, size() - 1); } /** * 获取一个元素 * * @param index * @param lower * @param upper * @return */ private Node<E> getNode(int index, int lower, int upper) { Node<E> node; //验证是否合法 if (index < lower || index > upper) { throw new IndexOutOfBoundsException(); } // if (index < size() / 2) { node = beginMarker.next; for (int i = 0; i < index; i++) { node = node.next; } } else { node = endMarker; for (int i = size(); i > index; i--) { node = node.prev; } } return node; } /** * 替换值 * * @param index * @param item * @return */ public E set(int index, E item) { Node<E> node = getNode(index); E data = node.data; node.data = item; return data; } /** * 删除一个元素 * * @param index * @return */ public E remove(int index) { return remove(getNode(index)); } /** * 删除一个节点 * * @param node * @return */ private E remove(Node<E> node) { node.next.prev = node.prev; node.prev.next = node.next; size--; modCount++; return node.data; } /** * 向头节点添加元素 * * @param node * @param item */ private void addBefore(Node<E> node, E item) { Node<E> newNode = new Node<>(item, node.prev, node); newNode.prev.next = newNode; node.prev = newNode; size++; modCount++; } @Override public Iterator<E> iterator() { return new LinkedListIterator(); } /** * 迭代器内部类 */ private class LinkedListIterator implements Iterator<E> { private Node<E> current = beginMarker.next; private int expModCount = modCount; private boolean okToRemove = false; @Override public boolean hasNext() { return current != endMarker; } @Override public E next() { if (modCount != expModCount) { throw new ConcurrentModificationException(); } if (!hasNext()) { throw new NoSuchElementException(); } E nextItem = current.data; current = current.next; okToRemove = true; return nextItem; } @Override public void remove() { if (modCount != expModCount) { throw new ConcurrentModificationException(); } if (!okToRemove) { throw new NoSuchElementException(); } MyLinkedList.this.remove(current.prev); expModCount++; okToRemove = false; } } }
四、常见算法
4.1 合并两个有序链表
问题描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 # 示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] # 示例 2: 输入：l1 = [], l2 = [] 输出：[] # 示例 3： 输入：l1 = [], l2 = [0] 输出：[0] # 提示： - 两个链表的节点数目范围是 [0, 50] - -100 <= Node.val <= 100 - l1 和 l2 均按非递减顺序排列
题解：
/** * 合并两个有序链表 * * @param l1 * @param l2 * @return */ public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { //如果l1为空就直接输出l2 if (l1 == null) { return l2; //如果l2为空就直接输出l1 } else if (l2 == null) { return l1; //比较l1和l2的值 } else if (l1.val < l2.val) { //进行递归操作 l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } }
4.2 删除链表中重复的元素
问题描述：
题目： 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素只出现一次 。返回同样按升序排列的结果链表 示例 1： 输入：head = [1,1,2] 输出：[1,2] 示例 2： 输入：head = [1,1,2,3,3] 输出：[1,2,3]
题解：
/** * 删除链表的重复元素 * * @param head * @return */ public ListNode deleteDuplicates(ListNode head) { if (head == null) { return null; } ListNode node = head; while (node.next != null) { //比较当前元素和下一个元素的值 if (node.val == node.next.val) { //删除操作 node.next = node.next.next; } else { node = node.next; } } return head; }
4.3 旋转链表
问题描述：
给你单链表的头节点 `head` ，请你反转链表，并返回反转后的链表。 示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 示例 2： 输入：head = [1,2] 输出：[2,1] 示例 3： 输入：head = [] 输出：[]
题解：
/** * 迭代方式 * * @param head * @return */ public static ListNode reverseList1(ListNode head) { //定义被反转的新链表 ListNode prev = null; //旧链表 ListNode curr = head; while (curr != null) { //获取旧链表的下一个节点 ListNode next = curr.next; //旧链表的下一个节点指向新链表 curr.next = prev; //将旧链表复制到新链表 prev = curr; //将旧链表更新为旧链表的下一个节点 curr = next; } return prev; } /** * @param head * @return */ public static ListNode reverseList2(ListNode head) { //递归的终止状态 //等于空或只有一个值则返回原链表 if (head == null || head.next == null) { return head; } //进行递归 ListNode newHead = reverseList2(head.next); head.next.next = head; head.next = null; return newHead; }
