数据结构与算法-单链表

数据结构讨论的是数据的存储方式，常用的数据结构分为两大类，一类是线性结构，一类是非线性结构。线性结构是一对一的关系，非线性结构是一对多，或者多对多的关系。链表，栈，队列等数据结构是线性结构；树，图等数据结构是非线性结构。

链表

链表是通过指针将一组零散的内存块串连在一起，我们称这个内存块为链表的结点。结点一般有指针域和数据域两个部分，不同类型的链表，指针域有所不同。

单链表

单链表是指每个结点有且只有一个后继指针指向下一个结点，并且最后一个结点的后继指针为 NULL。

链表中第一个结点称之为头结点，最后一个结点称之为尾结点。头结点用来记录链表的基地址，有了头结点，我们可以遍历整个链表；尾结点的后继指针为空，表示这是链表的最后一个结点。头结点不存放数据，只存放指向首结点的指针域，引入头结点的目的是为了方面链表的插入和删除操作。

结点

单链表的结点由数据域和一个指向下一个结点的指针域组成。

public class ListNode {
    int id;
    String name;
    ListNode next;

    public ListNode(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

ListNode 类定义了一个单链表的结点，id 和 name 是数据域，next 是指向下一个结点的指针域。下一个结点和当前结点一样都是 ListNode 类型。

创建单链表

头插法建立单链表

头插法建立单链表是将每次创建的结点都插入到头结点后面，作为链表头结点后面的第一个结点。插入新结点时，要先将新插入结点的 next 指针先指向头结点的下一个结点，再将头结点的 next 指针指向新插入的结点。如果先将头结点的 next 指针指向了新插入的结点，就会导致链表断开，这样就找不到后面的结点了。

// 头结点，辅助结点便于链表的操作
ListNode head = new ListNode(0, "");

/**
  * 头插法：每次插入的结点成为链表中的第一个结点
  * @param node 结点
  */
public void headCreateSingleLinkedList(ListNode node) {
    // 链表为空，直接插入到头结点后面；链表不为空，新结点插入到非头结点的第一个结点前面
    if (head.next == null) {
        // 头结点next域指向新结点
        head.next = node;
        // 结点的next域为空
        node.next = null;
    } else {
        // 新结点指向头结点的下一个结点
        node.next = head.next;
        // 头结点指向新结点，新结点成为新的非头结点之外的第一个结点
        head.next = node;
    }
}

尾插法建立单链表

尾插法建立单链表是将每次创建的结点依次链接在前一个结点的后面，作为链表的尾结点。

// 头结点，辅助结点便于链表的操作
ListNode head = new ListNode(0, "");

/**
  * 尾插法：每次插入的结点成为链表中的最后一个结点
  * @param node 结点
  */
public void tailCreateSingleLinkedList(ListNode node) {
    // 辅助变量用来找到最后一个结点
    ListNode temp = head;
    // 循环遍历找到最后一个结点
    while (temp.next != null) {
        temp = temp.next;
    }
    // 将新的结点链接到最后
    temp.next = node;
    // 最后一个结点的next域为空
    node.next = null;
}

插入结点

链表插入结点不需要像数组一样移动元素，只需要修改待插入位置相邻结点的指针即可。

链表插入结点的时间复杂度为 O(1)，但是链表在插入元素前需要先找到待插入的位置，而单链表只能从头结点开始按顺序往下依次查找，所以查找的时间复杂度为 O(n)，综合来看，**单链表插入结点的时间复杂度为 O(n)**。

链表在插入结点时，要先将待插入结点的 next 指针指向待插入位置的下一个结点，然后将前一个结点的 next 指针指向待插入的结点。如果先将待插入位置前一个结点的 next 指针先指向了 待插入的结点，就会造成链表断开，后面的结点就丢失了。

/**
  * 插入结点，在给定索引位置后插入
  * 先将要插入的结点的next域指向要插入位置的下一个结点
  * 再将要插入位置前的结点的next域指向要插入的结点
  * @param index 结点索引
  * @param node 待插入的结点
  */
public void addListNode(int index, ListNode node) {
    ListNode temp = head;
    int position = 0;
    // 头结点为空，链表不存在
    if (head == null) {
        System.out.println("链表不存在，无法插入！");
        return;
    }
    // 索引为负数，或者大于链表长度无法插入
    if (index > singleLinkedListLength() || index < 0) {
        System.out.println("结点插入位置非法！");
        return;
    }
    // 在头结点后面插入
    if (index == 0) {
        headCreateSingleLinkedList(node);
        return;
    }
    // 任意其他位置插入
    while (temp.next != null) {
        // 索引位置后移
        position++;
        temp = temp.next;
        // 找到要插入的位置
        if (position == index) {
            // 要插入的结点先连接到后一个结点，否则链表会断开
            node.next = temp.next;
            temp.next = node;
            break;
        }
    }
}

删除结点

删除结点只需要将要删除结点的前一个结点的 next 指针直接指向要删除结点的下一个结点即可。

和插入结点相同，删除结点的时间复杂度为 O(1)，但是查询要删除的结点时间复杂度为 O(n)，所以**删除结点的时间复杂度还是 O(n)**。

插入结点只需要找到要插入的结点位置的结点即可，删除结点需要找到待删除的结点和它的前一个结点，因为需要将前一个结点的 next 指针指向待删除结点的下一个结点。

/**
  * 删除结点，根据指定的名称删除
  * 找到要删除结点的位置和前一个位置，将前一个位置的next域指向要删除结点的下一个结点
  * @param name 结点名称
  */
public void deleteListNode(String name) {
    // 到删除的结点
    ListNode deleteNode;
    // 辅助变量找到删除结点的位置
    ListNode temp1 = head;
    // 辅助变量找到删除结点的前一个位置
    ListNode temp2 = head;
    // 找到结点标志位
    boolean flag = false;
    // 要删除的结点位置索引
    int position = 0;
    // 要删除的结点前一个结点的位置索引
    int previous = 0;
    // 链表不存在
    if (head == null) {
        System.out.println("链表不存在，无法删除！");
        return;
    }
    // 只有头结点
    if (head.next == null) {
        System.out.println("链表为空，无法删除！");
        return;
    }
    // 找到要删除的结点位置
    while (temp1.next != null) {
        position++;
        temp1 = temp1.next;
        // 找到结点
        if (name.equals(temp1.name)) {
            flag = true;
            break;
        }
    }
    if (!flag) {
        System.out.println("没找到要删除的结点！");
        return;
    }
    // 只有一个非头结点之外的结点
    if (position == 1 && singleLinkedListLength() == 1) {
        head.next = null;
        return;
    }
    // 找到要删除结点的前一个位置
    while (temp2.next != null) {
        // 要删除的结点指向前一个结点的下一个位置
        deleteNode = temp2.next;
        if (previous == position-1) {
            // 删除最后一个结点
            if (position == singleLinkedListLength()) {
                temp2.next = null;
                return;
            }
            // 将前一个位置的next域指向下一个结点
            temp2.next = deleteNode.next;
            // 删除结点的next域置空
            deleteNode.next = null;
            break;
        }
        previous++;
        temp2 = temp2.next;
    }
}

单链表的应用

反转单链表

单链表反转，将链表结点按顺序依次取下，按照头插法依次插入到一个新的头结点后面，再把原来的头结点指向指向新的头结点的下一个结点即可。

// 头结点，辅助结点便于链表的操作
ListNode head = new ListNode(0, "");

/**
  * 反转单链表
  * new一个新的头节点，将原来的链表上的节点一个一个取下，按头插法插入新的头节点后面
  * 最后把原来的头节点指向新的头节点的next域
  */
public void reserveSingleLinkedList() {
    // 链表为空或者只有一个节点，不用反转
    if (head.next == null || head.next.next == null) {
        System.out.println("无须反转！");
        return;
    }
    // 要反转的节点
    ListNode current = head.next;
    // 记录当前要反转节点的下一个节点
    ListNode next;
    // 定义一个新的头节点
    ListNode newHead = new ListNode(0, "");
    while (current != null) {
        // 反转前记录下当前节点的下一个节点位置
        next = current.next;
        // 当前节点插入到新的头节点的后面
        current.next = newHead.next;
        // 往后移动一个位置继续下一个节点的反转
        newHead.next = current;
        current = next;
    }
    // 原来的头节点指向新的头节点
    head.next = newHead.next;
}

合并两个有序单链表

如果两个链表都不为空，依次比较大小，将较小的一个节点插入到头结点的后面，如果只有一个链表不为空，直接插到链表最后面。

/**
  * 合并两个有序链表
  * 如果两个链表都不为空，依次比较大小，将较小的一个节点插入到头结点的后面
  * 如果只有一个链表不为空，直接插到链表最后面
  * @param list 链表
  */
public void mergeSingleLinkedList(SingleLinkedList list) {
    // 指向当前链表的头结点
    ListNode p = this.head;
    // 指向当前链表头节点的下一个节点
    ListNode p1 = this.head.next;
    // 指向第二个量表头节点的下一个节点
    ListNode p2 = list.head.next;
    // 两个链表都不为空
    while (p1 != null && p2 != null) {
        // 把id小的那个链表的节点挂在p后面
        if (p1.id > p2.id) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p往后移动一个位置
        p = p.next;
    }
    // 链表1多余的节点挂在p后面
    if (p1 != null) {
        p.next = p1;
    }
    // 链表2多余的节点挂在p后面
    if (p2 != null) {
        p.next = p2;
    }
}

删除倒数第k个结点

倒数第 k 个结点是正数第 n-k+1 个结点，找到删除节点的前一个节点，将前一个节点指向要删除节点的下一个节点。

/**
  * 删除倒数第k个元素
  * 倒数第k个节点是正数第n-k+1个节点
  * 找到删除节点的前一个节点，将前一个节点指向要删除节点的下一个节点
  * @param k 删除元素的倒数位置
  */
public void deleteKFromLastNode(int k) {
    // 指向头节点
    ListNode p1 = head;
    // 指向头节点的下一个节点
    ListNode p2 = head.next;
    int position = 0;
    if (p2 == null) {
        System.out.println("链表为空！");
        return;
    }
    // 倒数第k个节点的位置
    int length = singleLinkedListLength() - k + 1;
    while (p2 != null) {
        // 记录当前节点的位置
        position++;
        // 当前节点等于倒数第k个节点
        if (length == position) {
            // 删除倒数第k个节点
            p1.next = p2.next;
            break;
        }
        // 往后移动继续寻找
        p2 = p2.next;
        p1 = p1.next;
    }
}

这里也可以用双指针实现，复杂度更低。

获取单链表中间结点

使用双指针遍历，两个指针距离两个位置，当前面的指针到达链表尾部时，后面一个指针指向的位置就是中间节点的位置。

/**
  * 获取单链表的中间节点
  * 使用双指针遍历，两个指针距离两个位置，当前面的指针到达链表尾部时，
  * 后面一个指针指向的位置就是中间节点的位置
  */
public void getMiddleNode() {
    // 第一个辅助变量寻找中间节点
    ListNode p1 = head.next;
    // 第二个辅助变量
    ListNode p2;
    if (p1 == null) {
        System.out.println("链表为空！");
        return;
    }
    p2 = p1.next;
    if (p2 == null) {
        System.out.println("只有一个节点！");
        return;
    }
    // 前面指针的next不为空就继续遍历
    while (p2.next != null) {
        // 后面的指针往后移动一个位置
        p1 = p1.next;
        // 如果前面一个指针的后面只有一个节点，则遍历结束
        if (p2.next.next == null) {
            break;
        }
        // 前面的指针移动两个位置
        p2 = p2.next.next;
    }
    System.out.println("链表的中间节点为" + p1.id + ",名称为" + p1.name);
}