03、数据结构与算法 - 实战：单链表

链表是一种用于存储数据集合的数据结构

属性：

1、 相邻的元素之间通过指针连接
2、 最后一个元素的后继指针值为null
3、 链表的长度是可变的
4、 链表的空间能够按需分配

链表通常是指单向链表，它包括多个结点，每个结点有一个后继元素的next指针。表中最后一个结点的next指针值为null，表示该链表的结束。

链表的基本操作主要有三个

1、 遍历链表；
2、 向链表中插入一个元素；
3、 从链表中删除一个元素；

下面是一个链表的类型声明：

public class ListNode {
   
     

    /**
     * 结点数据域
     */
    private int data;   

    /**
     * 结点的next指针
     */
    private ListNode next;  

    /**
     * 有参构造函数
     * @param data 节点数据
     */
    public ListNode(int data) {
        this.data = data;
    }

    /**
     * @return the data
     */
    public int getData() {
        return data;
    }

    /**
     * @param data the data to set
     */
    public void setData(int data) {
        this.data = data;
    }

    /**
     * @return the next
     */
    public ListNode getNext() {
        return next;
    }

    /**
     * @param next the next to set
     */
    public void setNext(ListNode next) {
        this.next = next;
    }
}

1、 求链表的长度；

/**
 * 获取链表的长度
 * @param headNode 头结点
 * @return 链表的长度
 */ 
public static int getLength(ListNode headNode) {
    int length = 0;
    ListNode currentNode = headNode;
    while (currentNode != null) {
        length++;
        currentNode = currentNode.getNext();
    }
    return length;
}

2、 遍历链表；

/**
 * 遍历链表
 * @param headNode 头结点
 */
public static void traverseLinkedList(ListNode headNode) {
    ListNode currentNode = headNode;
    while (currentNode != null) {
        System.out.print(currentNode.getData() + " ");
        currentNode = currentNode.getNext();
    }
    System.out.println();
}

3、 根据位置获取相应的结点；

/**
 * 根据位置获取结点
 * @param headNode 链表的头结点
 * @param position 置位
 * @return 位置结点
 */
public static ListNode getNodeByPosition(ListNode headNode, int position) {

    // 检查需要查询的位置是否合法
    int length = getLength(headNode);
    if (position > length + 1 || position < 1) {
        System.out.println("查询的位置不合法，有效的位置为：1 ~ " + (length + 1));
        return null;
    } 

    int count = 1;
    ListNode currentNode = headNode;
    while ((currentNode != null) && (count != position)) {
        count++;
        currentNode = currentNode.getNext();
    }
    return currentNode;
}

4、 根据位置插入结点；

/**
 * 插入新结点
 * @param headNode 头结点
 * @param nodeToInsert 要插入的新结点
 * @param position 要插入的位置
 */
public static ListNode insertLinkedListNode(ListNode headNode, ListNode nodeToInsert, int position) {

    /*
     * 判断链表是否存在
     * 当链表不存在直接返回nodeToInsert作为链表的头结点
     */
    if (headNode == null) {
        return nodeToInsert;
    }

    /*
     * 检查需要插入的位置是否合法
     */
    int length = getLength(headNode);
    if (position > length + 1 || position < 1) {
        System.out.println("插入的位置不合法，有效的位置为：1 ~ " + (length + 1));
        return headNode;
    } 

    /*
     * 插入新结点
     * 1.向链表的开头插入新的结点
     *    更新新结点的next指针，使其指向当前链表的表头
     *    更新当前链表的表头指针的值，使其指向新结点
     * 2.向单链表的尾部插入新结点
     *    使新结点的next指针指向null
     *    使当前链表的最后结点的next指针指向新结点
     * 3.向单链表的中间插入新结点
     *     先遍历找到位置结点的前驱结点
     *   将前驱结点next指针指向的结点赋值给新结点的next指针
     *   使前驱结点的next指针指向新结点
     */
    if (position == 1) {
        // 在单链表开头插入结点
        nodeToInsert.setNext(headNode);
        return nodeToInsert;
    } else {
        // 在链表中间或者尾部插入结点
        int count = 1;
        ListNode previousNode = headNode;
        while(count < position - 1) {
            previousNode = previousNode.getNext();
            count++;
        }
        ListNode currentNode = previousNode.getNext();
        nodeToInsert.setNext(currentNode);
        previousNode.setNext(nodeToInsert);
    }
    return headNode;
}

5、 根据位置删除结点；

/**
 * 根据位置删除结点
 * @param headNode 头结点
 * @param position 结点位置
 * @return 删除位置结点后的链表
 */
public static ListNode deleteLinkedListNode(ListNode headNode, int position) {

    /*
     * 检查删除的位置是否合法
     */
    int length = getLength(headNode); 
    if (position > length || position < 1) {
        System.out.println("删除的位置不合法，有效的位置为：1 ~ " + (length + 1));
        return headNode;
    }

    /*
     * 单链表删除结点
     * 1.删除单链表的头结点
     *     创建一个临时结点指向表头指针指向的头节点
     *   修改表头指针，使其指向下一个结点，并移除临时结点
     * 2.删除单链表的最后一个结点
     *    先遍历找到尾结点的前驱结点
     *    使尾结点的next指针指向null
     *   移除单链表的尾结点
     * 3.删除单链表的中间结点
     *    先遍历找到删除结点的前驱结点
     *    使前驱结点的next指针指向删除结点next指针指向的值
     *   移除单链表的删除结点
     */
    if (position == 1) {
        // 删除单链表的头结点
        ListNode newHaedNode = headNode.getNext(); 
        headNode = null;
        return newHaedNode;
    } else {
        // 删除单链表的中间结点或者尾结点
        int count = 1;
        ListNode previousNode = headNode;
        while(count < position - 1) {
            previousNode = previousNode.getNext();
            count++;
        }
        ListNode nodeToDelete = previousNode.getNext();
        previousNode.setNext(nodeToDelete.getNext());
        nodeToDelete = null;
    }
    return headNode;
}

单链表的基本操作先整理到这，下面将整理一些关于单链表的经典题目。
注：最近在复习数据结构，文章的内容主要根据《数据结构与算法经典问题分析》Java语言描述一书整理而来