链表-我的基础算法刷题之路（二）-爱代码爱编程

本篇博客旨在整理记录自己学习链表的一些知识，以及力扣上链表题解，同时希望可给小伙伴一些帮助。本人也是算法小白，水平有限，如果文章中有什么错误之处，希望小伙伴们可以在评论区指出来，共勉 💪。

链表的概念

顺序表和链表都是线性表，也是最基本的数据结构。接下来带大家先稍微了解一下顺序表，再了解链表。

顺序表：顺序表是使用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，底层就是一个数组。

• 常见的线性表：顺序表、链表、栈、队列、字符串，线性表在逻辑上是线性结构，在物理上存储时通常以数组和链式结构的形式存储。

链表(linked list)：是一种物理存储结构上的非连续存储结构。有人可能好奇数组呢，数组是一种线性数据结构，用于存放相同的数据类型的集合容器。 数据元素的逻辑顺序是通过链表中的引用链接次序实现的（就是由一个个节点组成的，这些节点逻辑上连续，物理上不连续）。

由于不必须按顺序存储，链接在插入的时候可以达到O(1)的复杂度，比另一个线性表顺序表快得多，但是查找以恶搞节点或者访问特点编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表的分类

链表有：单向、双向、带头、不带头、循环

• 单向：后继指针指向下一个结点

  A

  B

  C

• 双向：指针可指向前驱也可指向后继

  A

  B

  C

• 带头：是只会有一个引用一直指向头节点（名为head），并且它的指向一直都不会变，即是一个傀儡节点。

  head头指针

  data头结点

  A首元素

  B

  CNull

• 不带头：也是会有一个引用指向头结点（名为head），但它的指向是可以发生改变的。

  L头指针

  A首元素

  B

  C

  DNull

• 循环：链表的最后一个节点的 next 域存储的是头节点的地址，此时的链表就是一个环状的。

  A

  B

  C

  D

非循环可排列组合为：八种结构

• 带头循环单向
• 带头，非循环单向
• 不带头，循环单向
• 不带头，非循环双向
• 带头，循环双向
• 带头，非循环双向
• 不带头，循环双向
• 不带头，非循环

其中重要的是：单向、不带头、非循环和双向，不带头，非循环

链表代码

单向链表：

//ListNode代表一个节点
class ListNode{
    public int val;
    public ListNode next;

    //构造函数
    public ListNode(int a){
        this.val = a;
    }
}
public class Linkedlist {

    public ListNode head;//链表的头

    // // 创建列表
    public void creatList() {
        ListNode listNode1 = new ListNode(11);
        ListNode listNode2 = new ListNode(22);
        ListNode listNode3 = new ListNode(33);
        ListNode listNode4 = new ListNode(44);
        ListNode listNode5 = new ListNode(55);

        this.head = listNode1;

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

    }

    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
    /*if(this.head == null){
        this.head = node;
    }else{
        node.next = this.head;
        this.head = node;
    }*/
    }

    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {
            this.head = node;
        } else {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //打印顺序表
    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度
    public int Size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //找到index位置的前一位置的地址
    public ListNode findIndex(int index) {
        ListNode cur = head.next;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        if (index < 0 || index > Size()) {
            return;
        }
        if (index == 0) {          //相当于头插法
            addFirst(data);
            return;
        }
        if (index == Size()) {      //相当于尾插法
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);//找到index位置前一位置的地址
        ListNode node = new ListNode(data);//初始化node
        node.next = cur.next;
        cur.next = node;
    }

    //找到key的前驱（前一节点）
    public ListNode searchPrev(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (this.head == null) {
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if (cur == null) {
            return;             //没有要删除的节点
        }
        ListNode del = cur.next;//定义要删除的节点
        cur.next = del.next;
    }

    //删除所有值为key的节点
    public ListNode removeAllKey(int key) {
        if (this.head == null) {
            return null;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (this.head.val == key) {
            this.head = this.head.next;
        }
        return this.head;
    }

    //清空链表
    public void clear() {
        while (this.head != null) {
            ListNode curNext = this.head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }
}

双向链表：

/**
 * 自己实现链表
 * @param <E> 泛型，表示容器当中存储数据的数据类型
 */
public class MyLinkedList<E> implements MyCollection<E> {
​
  // 表示链表当中数据的个数
  private int size = 0;
​
  // 链表当中第一个节点
  private Node<E> first;
​
  // 表示链表当中最后一个节点
  private Node<E> last;
​
  @Override
  public boolean add(E o) {
    return append(o);
  }
​
  @Override
  public boolean add(int index, E o) {
    Node<E> node = findNodeByIndex(index);
    insertBeforeNode(node, o);
    size++;
    return true;
  }
​
  /**
   * 在节点数据 node 之后插入数据 o
   * @param node
   * @param o
   */
  void insertAfterNode(Node<E> node, E o) {
    if (node == null)
      throw new NullPointerException();
    // newNode 前面的节点为 node 后面的节点是 node.next
    Node<E> newNode = new Node<>(o, node, node.next);
    if (node.next != null)
      node.next.prev = newNode;
    if (node == last)
      last = newNode;
    node.next = newNode;
  }
​
​
  /**
   * 在节点 node 之前插入数据 o
   * @param node
   * @param o
   */
  void insertBeforeNode(Node<E> node, E o) {
    if (node == null)
      throw new NullPointerException();
    // newNode 前面你的节点为 node.prev 后面的节点为 node
    Node<E> newNode = new Node<>(o, node.prev, node);
    if (node.prev != null)
      node.prev.next = newNode;
    else
      first = newNode;
    node.prev = newNode;
  }
​
  /**
   * 根据下标找节点
   * @param index
   * @return
   */
   Node<E> findNodeByIndex(int index) {
     if (index >= size)
       throw new RuntimeException("输入 index 不合法链表中的数据个数为 " + size);
    Node<E> x;
    // 首先看看 index 和 size / 2 的关系
    // 这里主要是看链表的首和尾部谁距离 index 位置近，那头近就从哪头遍历
    // size >> 1 == size / 2
    if (index < (size >> 1)) {
      x = first;
      for (int i = 0; i < index; i++)
        x = x.next;
    } else {
      x = last;
      for (int i = size - 1; i > index; i--)
        x = x.prev;
    }
    return x;
  }
​
  void removeNode(Node<E> node) {
     if (node == null)
       throw new NullPointerException();
     if (node.prev != null)
       node.prev.next = node.next;
     if (node.next != null)
       node.next.prev = node.prev;
  }
​
  @Override
  public boolean remove(E o) {
     Node<E> start = first;
     while (start != null) {
       if (start.item.equals(o))
         removeNode(start);
       start = start.next;
     }
     size--;
    return true;
  }
​
  /**
   * 根据下标删除某个节点
   * @param index
   * @return
   */
  @Override
  public boolean remove(int index) {
    // 首先找到第 index 个数据对应的节点
    Node<E> node = findNodeByIndex(index);
    // 删除节点
    removeNode(node);
    size--;
    return true;
  }
​
  @Override
  public boolean append(E o) {
    final Node<E> l = last;
    // 新增的节点需要将 prev 指向上一个节点，上一个节点就是链表的 last 节点
    // 新增节点的下一个节点就 null
    final Node<E> newNode = new Node<>(o, last, null);
    last = newNode;
    if (first == null) {
      // 如果链表当中还没有节点，就将其作为第一个节点
      first = newNode;
    }else {
      // 如果链表当中已经有节点，需要将新增的节点连接到链表的尾部
      l.next = newNode;
    }
    size++;
    return true;
  }
​
  @Override
  public int size() {
    return size;
  }
​
  @Override
  public boolean isEmpty() {
    return size == 0;
  }
​
  @Override
  public boolean contain(E o) {
     Node<E> start = first;
     while (start != null) {
       if (start.item.equals(o))
         return true;
       start = start.next;
     }
    return false;
  }
​
  private static class Node<E> {
    // 指向节点的真实存储的数据
    E item;
    // 前向指针：指向前一个数据
    Node<E> prev;
    // 后向指针：指向后一个数据
    Node<E> next;
    public Node(E item, Node<E> prev, Node<E> next) {
      this.item = item;
      this.prev = prev;
      this.next = next;
    }
  }
​
  @Override
  public String toString() {
​
     if (first == null)
       return "[]";
​
    StringBuilder builder = new StringBuilder();
    builder.append("[");
    Node<E> start = first;
    builder.append(start.item.toString());
    start = start.next;
    while (start != null) {
      builder.append(", ").append(start.item.toString());
      start = start.next;
    }
    builder.append("]");
    return builder.toString();
  }
​
  public static void main(String[] args) {
    MyLinkedList<Integer> list = new MyLinkedList<>();
    System.out.println(list.contain(100));
    for (int i = 0; i < 10; i++) {
      list.add(i);
    }
    list.add(0, -9999);
    System.out.println(list.size() / 2);
    list.add(5, 9999);
    list.append(Integer.MAX_VALUE);
    System.out.println(list);
​
    list.remove(5);
    list.add(6, 6666);
    System.out.println(list);
    System.out.println(list.contain(6666));
  }
}

链表题目：

876.链表的中间结点：

难度：简单

题目：给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

解题代码：

class Solution {
    public ListNode middleNode(ListNode head) {
        // 快慢指针
        ListNode slow = head, fast = head;
        /** 慢指针走一步，快指针走两步；
        如果长度是单数，当快指针到结尾时，慢指针对应的就是中间节点；
        如果长度是双数，当快指针到结尾时，慢指针右边对应的就是中间节点；
        */
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

707. 设计链表

难度：中等

题目：你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

提示：

• 0 <= index, val <= 1000
• 请不要使用内置的 LinkedList 库。
• 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

解题代码：

//单链表
class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}
class MyLinkedList {
    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode head;

    //初始化链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    //获取第index个节点的数值
    public int get(int index) {
        //如果index非法，返回-1
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode currentNode = head;
        //包含一个虚拟头节点，所以查找第 index+1 个节点
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }

    //在链表最前面插入一个节点
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    //在链表的最后插入一个节点
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果 index 大于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        size++;
        //找到要插入节点的前驱
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    //删除第index个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}


//双链表
class ListNode{
    int val;
    ListNode next,prev;
    ListNode() {};
    ListNode(int val){
        this.val = val;
    }
}
class MyLinkedList {  

    //记录链表中元素的数量
    int size;
    //记录链表的虚拟头结点和尾结点
    ListNode head,tail;
    
    public MyLinkedList() {
        //初始化操作
        this.size = 0;
        this.head = new ListNode(0);
        this.tail = new ListNode(0);
        //这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
        head.next=tail;
        tail.prev=head;
    }
    
    public int get(int index) {
        //判断index是否有效
        if(index<0 || index>=size){
            return -1;
        }
        ListNode cur = this.head;
        //判断是哪一边遍历时间更短
        if(index >= size / 2){
            //tail开始
            cur = tail;
            for(int i=0; i< size-index; i++){
                cur = cur.prev;
            }
        }else{
            for(int i=0; i<= index; i++){
                cur = cur.next; 
            }
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        //等价于在第0个元素前添加
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        //等价于在最后一个元素(null)前添加
        addAtIndex(size,val);
    }
    
    public void addAtIndex(int index, int val) {
        //index大于链表长度
        if(index>size){
            return;
        }
        //index小于0
        if(index<0){
            index = 0;
        }
        size++;
        //找到前驱
        ListNode pre = this.head;
        for(int i=0; i<index; i++){
            pre = pre.next;
        }
        //新建结点
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;
        pre.next.prev = newNode;
        newNode.prev = pre;
        pre.next = newNode;
        
    }
    
    public void deleteAtIndex(int index) {
        //判断索引是否有效
        if(index<0 || index>=size){
            return;
        }
        //删除操作
        size--;
        ListNode pre = this.head;
        for(int i=0; i<index; i++){
            pre = pre.next;
        }
        pre.next.next.prev = pre;
        pre.next = pre.next.next;
    }
}

19.删除链表的倒数第N个结点

难度：中等

题目：给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

解题代码

class Solution {
    // 通过快慢指针来解决，类似于你要删除中间元素的题
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 定义一个伪节点，用于返回结果
        ListNode dumpy = new ListNode(0);
        dumpy.next = head;
        // 定义一个快指针，指向伪节点，用于遍历链表
        ListNode prev = dumpy;
        // 定义一个慢指针，
        ListNode tail = dumpy;
        // 让快指针先移动 n 步
        while (n > 0) {
            prev = prev.next;
            n--;
        }
        // 只要快指针不指向空，就继续循环
        while (prev.next != null) {
            //让快慢指针同时移动
            tail = tail.next;
            prev = prev.next;
        }
        // 这时慢指针移动到位置就是，要删除节点的前一个结点
        // 所以只要删除当前节点的下一个节点
        tail.next = tail.next.next;
        // 返回为指针指向的头节点
        return dumpy.next;
    }
}

24. 两两交换链表中的节点

难度：中等

题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

提示：

• 链表中节点的数目在范围[0, 100]内
• 0 < = Node.val <= 100

解题代码：

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
        dumyhead.next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode cur = dumyhead;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;       // 步骤一
            secondnode.next = firstnode; // 步骤二
            firstnode.next = temp;       // 步骤三
            cur = firstnode;   // cur移动，准备下一轮
        }
        return dumyhead.next;
    }
}

25. K 个一组翻转链表

难度：困难

题目：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

解题代码：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null){
            return head;
        }
        //定义一个假的节点。
        ListNode dummy=new ListNode(0);
        //假节点的next指向head。
        // dummy->1->2->3->4->5
        dummy.next=head;
        //初始化pre和end都指向dummy。pre指每次要翻转的链表的头结点的上一个节点。end指每次要翻转的链表的尾节点
        ListNode pre=dummy;
        ListNode end=dummy;

        while(end.next!=null){
            //循环k次，找到需要翻转的链表的结尾,这里每次循环要判断end是否等于空,因为如果为空，end.next会报空指针异常。
            //dummy->1->2->3->4->5 若k为2，循环2次，end指向2
            for(int i=0;i<k&&end != null;i++){
                end=end.next;
            }
            //如果end==null，即需要翻转的链表的节点数小于k，不执行翻转。
            if(end==null){
                break;
            }
            //先记录下end.next,方便后面链接链表
            ListNode next=end.next;
            //然后断开链表
            end.next=null;
            //记录下要翻转链表的头节点
            ListNode start=pre.next;
            //翻转链表,pre.next指向翻转后的链表。1->2 变成2->1。 dummy->2->1
            pre.next=reverse(start);
            //翻转后头节点变到最后。通过.next把断开的链表重新链接。
            start.next=next;
            //将pre换成下次要翻转的链表的头结点的上一个节点。即start
            pre=start;
            //翻转结束，将end置为下次要翻转的链表的头结点的上一个节点。即start
            end=start;
        }
        return dummy.next;
    }
    //链表翻转
    // 例子：   head： 1->2->3->4
    public ListNode reverse(ListNode head) {
         //单链表为空或只有一个节点，直接返回原单链表
        if (head == null || head.next == null){
            return head;
        }
        //前一个节点指针
        ListNode preNode = null;
        //当前节点指针
        ListNode curNode = head;
        //下一个节点指针
        ListNode nextNode = null;
        while (curNode != null){
            nextNode = curNode.next;//nextNode 指向下一个节点,保存当前节点后面的链表。
            curNode.next=preNode;//将当前节点next域指向前一个节点   null<-1<-2<-3<-4
            preNode = curNode;//preNode 指针向后移动。preNode指向当前节点。
            curNode = nextNode;//curNode指针向后移动。下一个节点变成当前节点
        }
        return preNode;

    }
}

最后

建议结合力扣一起刷题🤣，有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~🙌🙌🙌