概念

链表是线性数据结构,是最简单的真正的动态数据结构.

特点

链表的数据存储在节点(node)中.

  • 优点:真正的动态,不需要处理固定容量问题
  • 缺点:丧失了随机访问的能力

    数组和链表对比

    数组

    数组最好用于索引有语意的情况
    最大的优点: 支持快速查询

    链表

    链表不适合用于索引有语意的情况
    最大的优点: 动态

    链表的实现

    ```java package cn.wllsrx.zoe.java.linkedlist;

/**

  • 增删改查时间复杂度都为O(n) *
  • 增删查只对链表头进行操作时间复杂度为O(1)

  • @author zoe **/ public class LinkedList {

    private class Node {

    1.  public E e;
    2.  public Node next;
    4.  public Node(E e, Node next) {
    5.      this.e = e;
    6.      this.next = next;
    7.  }
    9.  public Node(E e) {
    10.      this(e, null);
    11.  }
    13.  public Node() {
    14.      this(null, null);
    15.  }
    17.  @Override
    18.  public String toString() {
    19.      return e.toString();
    20.  }

    }

    /**

    • 虚拟头节点 */ private Node dummyHead; private int size;

      public LinkedList() { dummyHead = new Node(null, null); size = 0; }

      /**

    • 获取链表中的元素个数 *

    • @return 个数 */ public int getSize() { return size; }

      /**

    • 判断链表是否为空 *

    • @return 为空true 反之false */ public boolean isEmpty() { return size == 0; }

      /**

    • 在链表index位置添加元素 时间复杂度O(n) *
    • @param index 索引0开始

    • @param e 元素 */ public void add(int index, E e) { if (index < 0 || index > size) {

      1.  throw new IllegalArgumentException("Add failed. illegal index");

      } //dummyHead是索引0前面的一个元素 Node prev = dummyHead; //遍历index前一个位置的元素 for (int i = 0; i < index; i++) {

      1.  prev = prev.next;

      } prev.next = new Node(e, prev.next); size++;

      }

      /**

    • 在链表的头添加新的元素e 时间复杂度O(n) *

    • @param e 元素 */ public void addFirst(E e) { add(0, e); }

      /**

    • 在链表末尾添加元素 时间复杂度O(1) *

    • @param e 元素 */ public void addLast(E e) { add(size, e); }

      /**

    • 获取索引位置的元素 时间复杂度O(n) *
    • @param index 索引

    • @return 元素 */ public E get(int index) { //检查索引下标 this.checkIndex(index); //获取索引所在位置的元素,dummyHead.next是链表的第一个元素 Node cur = dummyHead.next; for (int i = 0; i < index; i++) {

      1.  cur = cur.next;

      } return cur.e; }

      /**

    • 获取链表第一个元素 *

    • @return E */ public E getFirst() { return get(0); }

      /**

    • 获取链表最后一个元素 *

    • @return E */ public E getLast() { return get(size - 1); }

      /**

    • 修改索引index位置的元素为e 时间复杂度O(n) *
    • @param index 索引

    • @param e 元素 */ public void set(int index, E e) { this.checkIndex(index); Node cur = dummyHead.next; for (int i = 0; i < index; i++) {

      1.  cur = cur.next;

      } cur.e = e; }

      /**

    • 删除索引位置的元素 时间复杂度O(n) *
    • @param index 索引

    • @return 被删除元素 */ public E remove(int index) { this.checkIndex(index); //索引位置的前一个元素 Node pre = dummyHead; for (int i = 0; i < index; i++) {

      1.  pre = pre.next;

      } //被删除索引位置的元素 Node del = pre.next; pre.next = del.next; del.next = null; size—; return del.e; }

      /**

    • 删除链表第一个元素 时间复杂度O(1) *

    • @return 被删除元素 */ public E removeFirst() { return remove(0); }

      /**

    • 删除链表最后一个元素 时间复杂度O(n) *

    • @return 被删除元素 */ public E removeLast() { return remove(size - 1); }

      /**

    • 检查索引是否合法 *

    • @param index 索引 */ private void checkIndex(int index) { if (index < 0 || index > size) {

      1.  throw new IllegalArgumentException("set failed. illegal index");

      } }

      /**

    • 判断元素是否存在 时间复杂度O(n) *
    • @param e 元素
    • @return 是否存在 */ public boolean contains(E e) { Node cur = dummyHead.next; while (cur != null) {
      1.  if (cur.e.equals(e)) {
      2.      return true;
      3.  }
      4.  cur = cur.next;
      } return false; }
  1. @Override
  2. public String toString() {
  3.     StringBuilder builder = new StringBuilder();
  4.     for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
  5.         builder.append(cur).append("->");
  6.     }
  7.     builder.append("null");
  8.     return builder.toString();
  9. }
  11. public static void main(String[] args) {
  12.     LinkedList<Integer> linkedList = new LinkedList<>();
  13.     for (int i = 0; i < 6; i++) {
  14.         linkedList.addFirst(i);
  15.         System.out.println(linkedList);
  16.     }
  17.     linkedList.add(2, 888);
  18.     System.out.println(linkedList);
  19.     linkedList.remove(2);
  20.     System.out.println(linkedList);
  21.     linkedList.removeFirst();
  22.     System.out.println(linkedList);
  23.     linkedList.removeLast();
  24.     System.out.println(linkedList);
  25. }

}

  1. <a name="3b94686a189018195ae9b7398eff1a73"></a>
  2. ## 使用链表实现栈
  3. <a name="cf8e8ae558b2d5517081b4777d961a68"></a>
  4. ### 栈接口
  5. ```java
  6. public interface Stack<E> {
  7.     /**
  8.      * 获取栈中元素个数
  9.      *
  10.      * 时间复杂度 O(1)
  11.      * @return int
  12.      */
  13.     int getSize();
  15.     /**
  16.      * 判断栈是否为空
  17.      *
  18.      * 时间复杂度 O(1)
  19.      * @return boolean
  20.      */
  21.     boolean isEmpty();
  23.     /**
  24.      * 在栈中添加元素e(入栈)
  25.      *
  26.      * 时间复杂度 O(1)均摊
  27.      * @param e 元素
  28.      */
  29.     void push(E e);
  31.     /**
  32.      * 从栈中取出元素(出栈)
  33.      *
  34.      * 时间复杂度 O(1)均摊
  35.      * @return E
  36.      */
  37.     E pop();
  39.     /**
  40.      * 查看栈顶元素
  41.      *
  42.      * 时间复杂度 O(1)
  43.      * @return E
  44.      */
  45.     E peek();
  47. }

链表实现栈

  1. /**
  2.  * 使用链表实现栈
  3.  *
  4.  * @author zoe
  5.  **/
  6. public class LinkedListStack<E> implements Stack<E> {
  7.     private final LinkedList<E> list;
  9.     public LinkedListStack() {
  10.         list = new LinkedList<>();
  11.     }
  13.     @Override
  14.     public int getSize() {
  15.         return list.getSize();
  16.     }
  18.     @Override
  19.     public boolean isEmpty() {
  20.         return list.isEmpty();
  21.     }
  23.     @Override
  24.     public void push(E e) {
  25.         list.addFirst(e);
  26.     }
  28.     @Override
  29.     public E pop() {
  30.         return list.removeFirst();
  31.     }
  33.     @Override
  34.     public E peek() {
  35.         return list.getFirst();
  36.     }
  38.     @Override
  39.     public String toString() {
  40.         return "Stack: top " +
  41.                 list;
  42.     }
  44.     public static void main(String[] args) {
  45.         LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
  46.         for (int i = 0; i < 7; i++) {
  47.             linkedListStack.push(i);
  48.             System.out.println(linkedListStack);
  49.         }
  50.         linkedListStack.pop();
  51.         System.out.println(linkedListStack);
  52.     }
  53. }

链表实现栈和数组实现栈的耗时比较

数组实现栈

  1. public class ArrayStack<E> implements Stack<E> {
  3.     Array<E> array;
  5.     public ArrayStack(int capacity) {
  6.         array = new Array<>(capacity);
  7.     }
  9.     public ArrayStack() {
  10.         array = new Array<>();
  11.     }
  14.     @Override
  15.     public int getSize() {
  16.         return array.getSize();
  17.     }
  19.     @Override
  20.     public boolean isEmpty() {
  21.         return array.isEmpty();
  22.     }
  24.     public int getCapacity() {
  25.         return array.getCapacity();
  26.     }
  28.     @Override
  29.     public void push(E e) {
  30.         //在数组末尾添加元素
  31.         array.addLast(e);
  32.     }
  34.     @Override
  35.     public E pop() {
  36.         return array.removeLast();
  37.     }
  39.     @Override
  40.     public E peek() {
  41.         return array.getLast();
  42.     }
  44.     @Override
  45.     public String toString() {
  46.         StringBuilder builder = new StringBuilder();
  47.         builder.append("Stack: ");
  48.         builder.append("[");
  49.         for (int i = 0; i < array.getSize(); i++) {
  50.             builder.append(array.get(i));
  51.             if (i != array.getSize() - 1) {
  52.                 builder.append(",");
  53.             }
  54.         }
  55.         builder.append("] top");
  56.         return builder.toString();
  57.     }
  59.     public static void main(String[] args) {
  60.         ArrayStack<Integer> stack = new ArrayStack<>();
  61.         for (int i = 0; i < 5; i++) {
  62.             //入栈
  63.             stack.push(i);
  64.             System.out.println(stack);
  65.         }
  66.         //出栈
  67.         stack.pop();
  68.         System.out.println(stack);
  69.     }
  70. }

耗时对比

  1. public class TestStack {
  2.     public static void main(String[] args) {
  3.         int opCount = 100000;
  4.         ArrayStack<Integer> arrayStack = new ArrayStack<>();
  5.         System.out.println("ArrayStack, time: " + testStack(arrayStack, opCount) + "s");
  6.         LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
  7.         System.out.println("LinkedListStack, time: " + testStack(linkedListStack, opCount) + "s");
  8.     }
  10.     public static double testStack(Stack<Integer> stack, int opCount) {
  11.         long startTime = System.nanoTime();
  12.         SecureRandom random = new SecureRandom();
  13.         for (int i = 0; i < opCount; i++) {
  14.             stack.push(random.nextInt(Integer.MAX_VALUE));
  15.         }
  16.         for (int i = 0; i < opCount; i++) {
  17.             stack.pop();
  18.         }
  19.         long endTime = System.nanoTime();
  20.         return (endTime - startTime) / 1000000000.0;
  21.     }
  22. }

使用链表实现队列

链表接口

  1. public interface Queue<E> {
  3.     /**
  4.      * 入队操作
  5.      *
  6.      * 时间复杂度 O(1) 均摊 ArrayQueue 和 LoopQueue同
  7.      * @param e 元素
  8.      */
  9.     void enqueue(E e);
  11.     /**
  12.      * 出队操作
  13.      *
  14.      * 时间复杂度 O(n)  ArrayQueue复杂度为O(n)  LoopQueue复杂度O(1) 均摊
  15.      * 出队拿出数组中第一个元素后,剩下的元素都要前移
  16.      * @return 元素
  17.      */
  18.     E dequeue();
  20.     /**
  21.      * 查看队列队首的元素
  22.      *
  23.      * 时间复杂度 O(1)  ArrayQueue 和 LoopQueue同
  24.      * @return 元素
  25.      */
  26.     E getFront();
  28.     /**
  29.      * 获取队列的数量
  30.      *
  31.      * 时间复杂度 O(1) ArrayQueue 和 LoopQueue同
  32.      * @return size
  33.      */
  34.     int getSize();
  36.     /**
  37.      * 判断队列是否为空
  38.      *
  39.      * 时间复杂度 O(1) ArrayQueue 和 LoopQueue同
  40.      * @return true为空, false反之
  41.      */
  42.     boolean isEmpty();
  43. }

链表实现队列

  1. public class LinkedListQueue<E> implements Queue<E> {
  3.     private class Node {
  4.         public E e;
  5.         public Node next;
  7.         public Node(E e, Node next) {
  8.             this.e = e;
  9.             this.next = next;
  10.         }
  12.         public Node(E e) {
  13.             this(e, null);
  14.         }
  16.         public Node() {
  17.             this(null, null);
  18.         }
  20.         @Override
  21.         public String toString() {
  22.             return e.toString();
  23.         }
  24.     }
  26.     private Node head, tail;
  27.     private int size;
  29.     public LinkedListQueue() {
  30.         head = null;
  31.         tail = null;
  32.         size = 0;
  33.     }
  36.     @Override
  37.     public void enqueue(E e) {
  38.         //如果队尾为空,说明队首也为空
  39.         if (tail == null) {
  40.             //直接在队尾添加节点
  41.             tail = new Node(e);
  42.             head = tail;
  43.         } else {
  44.             tail.next = new Node(e);
  45.             tail = tail.next;
  46.         }
  47.         size++;
  48.     }
  50.     @Override
  51.     public E dequeue() {
  52.         this.checkSize();
  53.         //出队是删除队首,也就是head
  54.         Node ret = head;
  55.         //把head指向之前head的下一个节点
  56.         head = ret.next;
  57.         //之前的head的下一个节点改为空
  58.         ret.next = null;
  59.         //修改head指向后队列可能为空
  60.         if (head == null) {
  61.             tail = null;
  62.         }
  63.         size--;
  64.         return ret.e;
  65.     }
  67.     private void checkSize() {
  68.         if (isEmpty()) {
  69.             throw new IllegalArgumentException("cannot dequeue from an empty queue");
  70.         }
  71.     }
  73.     @Override
  74.     public E getFront() {
  75.         this.checkSize();
  76.         return head.e;
  77.     }
  79.     @Override
  80.     public int getSize() {
  81.         return size;
  82.     }
  84.     @Override
  85.     public boolean isEmpty() {
  86.         return size == 0;
  87.     }
  89.     @Override
  90.     public String toString() {
  91.         StringBuilder builder = new StringBuilder();
  92.         builder.append("Queue: front ");
  93.         Node cur = head;
  94.         while (cur!=null){
  95.             builder.append(cur).append("->");
  96.             cur = cur.next;
  97.         }
  98.         builder.append("Null tail");
  99.         return builder.toString();
  100.     }
  102.     public static void main(String[] args) {
  103.         LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
  104.         for (int i = 0; i < 10; i++) {
  105.             //向队列中添加元素
  106.             linkedListQueue.enqueue(i);
  107.             System.out.println(linkedListQueue);
  108.             if (i % 3 == 2) {
  109.                 linkedListQueue.dequeue();
  110.                 System.out.println(linkedListQueue);
  111.             }
  112.         }
  113.     }
  114. }

数组队列,循环队列和链表队列耗时比较

数组队列

  1. public class ArrayQueue<E> implements Queue<E> {
  3.     Array<E> array;
  5.     public ArrayQueue(int capacity) {
  6.         array = new Array<>(capacity);
  7.     }
  9.     public ArrayQueue() {
  10.         array = new Array<>();
  11.     }
  13.     @Override
  14.     public void enqueue(E e) {
  15.         //向数组的末尾添加元素
  16.         array.addLast(e);
  17.     }
  19.     @Override
  20.     public E dequeue() {
  21.         //取出第一个元素
  22.         return array.removeFirst();
  23.     }
  25.     @Override
  26.     public E getFront() {
  27.         return array.getFirst();
  28.     }
  30.     @Override
  31.     public int getSize() {
  32.         return array.getSize();
  33.     }
  35.     @Override
  36.     public boolean isEmpty() {
  37.         return array.isEmpty();
  38.     }
  40.     public int getCapacity() {
  41.         return array.getCapacity();
  42.     }
  44.     @Override
  45.     public String toString() {
  46.         StringBuilder builder = new StringBuilder();
  47.         builder.append("Queue: ");
  48.         builder.append("front [");
  49.         for (int i = 0; i < array.getSize(); i++) {
  50.             builder.append(array.get(i));
  51.             if (i != array.getSize() - 1) {
  52.                 builder.append(",");
  53.             }
  54.         }
  55.         builder.append("] tail");
  56.         return builder.toString();
  57.     }
  59.     public static void main(String[] args) {
  60.         ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
  61.         for (int i = 0; i < 10; i++) {
  62.             //向队列中添加元素
  63.             arrayQueue.enqueue(i);
  64.             System.out.println(arrayQueue);
  65.             if (i % 3 == 2) {
  66.                 arrayQueue.dequeue();
  67.                 System.out.println(arrayQueue);
  68.             }
  69.         }
  70.     }
  71. }

循环队列

  1. public class LoopQueue<E> implements Queue<E> {
  3.     private E[] data;
  4.     private int front, tail;
  5.     private int size;
  7.     @SuppressWarnings("unchecked")
  8.     public LoopQueue(int capacity) {
  9.         data = (E[]) new Object[capacity + 1];
  10.         front = 0;
  11.         tail = 0;
  12.         size = 0;
  13.     }
  15.     public int getCapacity() {
  16.         return data.length - 1;
  17.     }
  19.     public LoopQueue() {
  20.         this(10);
  21.     }
  23.     @Override
  24.     public void enqueue(E e) {
  25.         if ((tail + 1) % data.length == front) {
  26.             resize(getCapacity() * 2);
  27.         }
  28.         data[tail] = e;
  29.         tail = (tail + 1) % data.length;
  30.         size++;
  31.     }
  33.     @SuppressWarnings("unchecked")
  34.     private void resize(int newCapacity) {
  35.         E[] newData = (E[]) new Object[newCapacity + 1];
  36.         for (int i = 0; i < size; i++) {
  37.             //新数组第一个元素对应的data是front,第二个元素是front+1,第三个是front+2,依次类推
  38.             //循环队列可能会产生数组越界
  39.             newData[i] = data[(i + front) % data.length];
  40.         }
  41.         data = newData;
  42.         front = 0;
  43.         tail = size;
  44.     }
  46.     @Override
  47.     public E dequeue() {
  48.         if (isEmpty()) {
  49.             throw new IllegalArgumentException("Cannot dequeue from an empty queue");
  50.         }
  51.         E ret = data[front];
  52.         data[front] = null;
  53.         front = (front + 1) % data.length;
  54.         size--;
  55.         //缩容
  56.         if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
  57.             resize(getCapacity() / 2);
  58.         }
  59.         return ret;
  60.     }
  62.     @Override
  63.     public E getFront() {
  64.         if (isEmpty()) {
  65.             throw new IllegalArgumentException("Cannot dequeue from an empty queue");
  66.         }
  67.         return data[front];
  68.     }
  70.     @Override
  71.     public int getSize() {
  72.         return size;
  73.     }
  75.     @Override
  76.     public boolean isEmpty() {
  77.         return front == tail;
  78.     }
  80.     @Override
  81.     public String toString() {
  82.         StringBuilder builder = new StringBuilder();
  83.         builder.append(String.format("Queue: size = %d,capacity = %d\n", size, getCapacity()));
  84.         builder.append("fount [");
  85.         for (int i = front; i != tail; i = (i + 1) % data.length) {
  86.             builder.append(data[i]);
  87.             if (i != size - 1) {
  88.                 builder.append(",");
  89.             }
  90.         }
  91.         builder.append("] tail");
  92.         return builder.toString();
  93.     }
  95.     public static void main(String[] args) {
  96.         LoopQueue<Integer> loopQueue = new LoopQueue<>();
  97.         for (int i = 0; i < 10; i++) {
  98.             //向队列中添加元素
  99.             loopQueue.enqueue(i);
  100.             System.out.println(loopQueue);
  101.             if (i % 3 == 2) {
  102.                 loopQueue.dequeue();
  103.                 System.out.println(loopQueue);
  104.             }
  105.         }
  106.     }
  107. }

耗时对比

  1. public class TestQueue {
  3.     public static void main(String[] args) {
  4.         int opCount = 100000;
  5.         System.out.println("数组队列ArrayQueue耗时:  " + testQueue(new ArrayQueue<>(), opCount) + "s");
  6.         System.out.println("循环队列LoopQueue耗时:  " + testQueue(new LoopQueue<>(), opCount) + "s");
  7.         System.out.println("链表队列LinkedListQueue耗时:  " + testQueue(new LinkedListQueue<>(), opCount) + "s");
  8.     }
  10.     private static double testQueue(Queue<Integer> q, int opCount) {
  11.         long startTime = System.nanoTime();
  12.         SecureRandom random = new SecureRandom();
  13.         for (int i = 0; i < opCount; i++) {
  14.             //入队操作
  15.             q.enqueue(random.nextInt(Integer.MAX_VALUE));
  16.         }
  17.         for (int i = 0; i < opCount; i++) {
  18.             //出队操作
  19.             q.dequeue();
  20.         }
  21.         long endTime = System.nanoTime();
  22.         return (endTime - startTime) / 1000000000.0;
  23.     }
  24. }

链表应用

移除链表元素(leetcode 203)

1. 要求

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

提示：
列表中的节点在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= k <= 50

2. Java不使用虚拟头节点实现

  1. public class LinkSolution {
  3.     private static class ListNode {
  4.         int val;
  5.         ListNode next;
  7.         ListNode() {
  8.         }
  10.         ListNode(int val) {
  11.             this.val = val;
  12.         }
  14.         ListNode(int val, ListNode next) {
  15.             this.val = val;
  16.             this.next = next;
  17.         }
  18.         //使用arr作为参数,创建链表,当前得listNode为链表头节点
  19.         public ListNode(int[] arr) {
  20.             if (arr == null || arr.length == 0) {
  21.                 throw new IllegalArgumentException("arr can not be empty");
  22.             }
  23.             //将数组第一个元素作为头节点
  24.             this.val = arr[0];
  25.             //当前节点
  26.             ListNode cur = this;
  27.             //循环遍历从第二个元素开始放到节点的下一节点
  28.             for (int i = 1; i < arr.length; i++) {
  29.                 cur.next = new ListNode(arr[i]);
  30.                 //将加入的节点赋值给当前节点,遍历添加这一节点的下一节点
  31.                 cur = cur.next;
  32.             }
  33.         }
  35.         @Override
  36.         public String toString() {
  37.             StringBuilder stringBuilder = new StringBuilder();
  38.             ListNode cur = this;
  39.             while (cur != null){
  40.                 stringBuilder.append(cur.val).append("->");
  41.                 cur = cur.next;
  42.             }
  43.             stringBuilder.append("null");
  44.             return stringBuilder.toString();
  45.         }
  46.     }
  48.     public static ListNode removeElements(ListNode head, int val) {
  49.         //处理头节点,所有头节点的下一节点也与val相等时循环处理
  50.         while (head != null && head.val == val) {
  51.             //若头节点与val相等,删除头节点
  52.             ListNode delNode = head;
  53.             //头节点改为将要删除的头节点的下一节点
  54.             head = head.next;
  55.             //删除节点的下一节点设为null
  56.             delNode.next = null;
  57.             //上面过程可直接写为head = head.next;
  58.             //head = head.next;
  59.         }
  60.         if (head == null) {
  61.             return null;
  62.         }
  63.         //待删除的前一个节点.prev是头节点,一定不是待删除的节点,
  64.         //前面已经对头节点做过处理,走到这一步说明头节点的val一定与val不相等
  65.         ListNode prev = head;
  66.         //循环头节点的下一个节点之后所有节点,判断是否删除,逻辑与头节点的删除逻辑相同
  67.         while (prev.next != null) {
  68.             if (prev.next.val == val) {
  69.                 ListNode delNode = prev.next;
  70.                 prev.next = delNode.next;
  71.                 delNode.next = null;
  72.                 //上面三行可直接写为
  73.                 //prev.next = prev.next.next;
  74.             } else {
  75.                 //不需要删除直接将prev直接后挪一个节点
  76.                 prev = prev.next;
  77.             }
  78.         }
  79.         return head;
  80.     }
  82. }

3. go实现

  1. type ListNode struct {
  2.     Val  int
  3.     Next *ListNode
  4. }
  6. func removeElements(head *ListNode, val int) *ListNode {
  7.     for head != nil && head.Val == val {
  8.         head = head.Next
  9.     }
  10.     if head == nil {
  11.         return head
  12.     }
  13.     pre := head
  14.     for pre.Next != nil {
  15.         if pre.Next.Val == val {
  16.             pre.Next = pre.Next.Next
  17.         } else {
  18.             pre = pre.Next
  19.         }
  20.     }
  21.     return head
  22. }

4. Java使用虚拟头节点实现

  1. public static ListNode removeElements1(ListNode head, int val) {
  2.         //创建虚拟头节点
  3.         ListNode dummyHead = new ListNode(-1);
  4.         //虚拟头节点得下一节点指向真实头节点
  5.         dummyHead.next = head;
  6.         //从第一个元素之前得节点开始,不需要处理头节点
  7.         ListNode prev = dummyHead;
  8.         while (prev.next != null) {
  9.             if (prev.next.val == val) {
  10.                 prev.next = prev.next.next;
  11.             } else {
  12.                 prev = prev.next;
  13.             }
  14.         }
  15.         return dummyHead.next;
  16.     }

5.所写方法测试

  1.  public static void main(String[] args) {
  2.         int[] nums = {1,2,6,3,4,5,6};
  3.         ListNode head = new ListNode(nums);
  4.         System.out.println(head);
  5.         System.out.println("不使用虚拟头节点: " + LinkSolution.removeElements(head,6));
  6.         System.out.println("使用虚拟头节点: " + LinkSolution.removeElements1(head,6));
  7.     }

项目demo