手写单链表

package top.wangyq.leetcode.design_list_node;

/**
 * 手动实现单链表
 * @author wangyongqiang
 */
public class SingleListNode {

    int val;
    SingleListNode next;
    SingleListNode(int x){
        val = x;
        this.next = null;
    }

    /**
     * 创建 ListNode
     * @param arr
     * @return
     */
    public static SingleListNode createLinkedList(int[] arr){
        if(arr == null || arr.length == 0){
            return null;
        }
        SingleListNode head = new SingleListNode(arr[0]);
        SingleListNode current = head;
        for (int i = 1; i < arr.length; i++) {
            current.next = new SingleListNode(arr[i]);
            current = current.next;
        }
        // 返回头节点，其他的元素通过遍历，并结合头节点依次指向下一个节点寻找即可
        return head;
    }

    /**
     * for遍历 ListNode
     */
    public static void iterListNodeByFor(SingleListNode head){
        for (SingleListNode p = head; p!=null; p = p.next){
            System.out.println("p.val = " + p.val);
        }
    }

    /**
     * while遍历 ListNode：核心判断条件都是当前节点不为空的时候输出当前节点的值
     */
    public static void iterListNodeByWhile(SingleListNode head){
        while (head != null){
            int val = head.val;
            head = head.next;
            System.out.println("val = " + val);
        }
    }

    /**
     * 在单链表头部插入新元素
     * @param head
     * @return
     */
    public static SingleListNode insertHeadListNode(SingleListNode head){
        if(head == null){
            return null;
        }
        // 直接创建一个新的节点
        SingleListNode singleListNode = new SingleListNode(666);
        // 将新节点的next指针指向当前的头节点
        singleListNode.next = head;
        return singleListNode;
    }

    /**
     * 在单链表尾部插入新元素
     * @param head
     * @return
     */
    public static SingleListNode insertTailListNode(SingleListNode head){
        if(head == null){
            return null;
        }
        // 直接创建一个新的节点
        SingleListNode singleListNode = new SingleListNode(999);
        // 创建当前的起始节点，将原始单链表赋值给临时变量，通过临时变量找到最后一个节点
        SingleListNode current = head;
        // 循环遍历到最后一个节点
        while (current.next != null){
            current = current.next;
        }
        // 将最后一个变量的next值赋值为新创建的listNode
        current.next = singleListNode;
        // 最后返回入参的Head单链表
        return head;
    }

    /**
     * 在第index个元素后添加元素，如果越界则直接返回原始数组
     * 原始数据：【9 6 1 7 8】
     * 在第3个元素后插入新的元素【222】
     *  1.next = 7 : 原始第3个元素的next指针指向的是数字7
     *  222.next = 7 : 现在需要把新元素【222】的指针指向7
     *  1.next = 222 : 当前元素的next则需要替换为新元素【222】
     * @param head
     * @param index 索引
     * @return
     */
    public static SingleListNode insertIndexListNode(SingleListNode head, int index){
        SingleListNode singleListNode = new SingleListNode(222);
        SingleListNode current = head;
        // 找到锁指定位置（位置从1开始）的元素，从1开始，比如当前index为3，则从【9 6 1 7 8】找到的值为“1”（current.val = 1）
        for (int i = 1; i < index; i++) {
            if (current == null || current.next == null) {
                // index 不合法，返回原链表
                System.out.println("链表插入：index 不合法，返回原链表");
                return head;
            }
            current = current.next;
        }
        // 当前cur为第3个元素，在第三个元素后插入一个新的元素，就需要将当前元素（1）的next（7）赋值给新变量（listNode）的next指针（7）
        singleListNode.next = current.next;
        // 当前元素（1）的next则为新元素（listNode），其val是111
        current.next = singleListNode;
        // 最后因为修改的只是cur的指向和listNode的指向，所以head头指针所指向的ListNode是不变的， 所以仍然可以通过遍历头指针去遍历当前单链表的所有元素
        return head;
    }

    /**
     * 删除第index个元素元素(未处理越界的问题)
     * 原始数据：【9 6 1 7 8】
     * @param head
     * @param index 索引
     * @return
     */
    public static SingleListNode deleteIndexListNode(SingleListNode head, int index) {
        // 1. 如果链表为空，直接返回 null
        if (head == null) {
            return null;
        }
        // 2. 如果要删除的索引是 0，即删除头节点
        if (index == 0) {
            // 将头节点的下一个节点作为新的头节点返回
            return head.next;
        }
        // 3. 否则，遍历链表，找到待删除节点的前一个节点
        SingleListNode current = head;
        int i = 1;
        // 遍历到删除节点的前一个节点
        while (current != null && i < index - 1) {
            current = current.next;
            i++;
        }
        // 4. 如果 index 越界，返回链表不做任何修改
        if (current == null || current.next == null) {
            // index 不合法，返回原链表
            System.out.println("链表删除：index 不合法，返回原链表");
            return head;
        }
        // 5. 删除目标节点
        current.next = current.next.next;
        return head;
    }

    public static void main(String[] args) {
        SingleListNode linkedList = SingleListNode.createLinkedList(new int[]{9, 6, 1, 7, 8});
        SingleListNode.iterListNodeByWhile(linkedList);
        System.out.println("==================1======================");
        SingleListNode headLinkedList = SingleListNode.insertHeadListNode(linkedList);
        SingleListNode.iterListNodeByWhile(headLinkedList);
        System.out.println("==================2======================");
        SingleListNode tailLinkedList = SingleListNode.insertTailListNode(linkedList);
        SingleListNode.iterListNodeByWhile(tailLinkedList);
        System.out.println("==================3======================");
        // 算法需求：在第三个元素之后追加新的节点，如果越界则返回原链表
        SingleListNode indexLinkedList = SingleListNode.insertIndexListNode(tailLinkedList, 3);
        SingleListNode.iterListNodeByWhile(indexLinkedList);
        System.out.println("==================4======================");
        SingleListNode deleteIndexSingleListNode = SingleListNode.deleteIndexListNode(linkedList, 3);
        SingleListNode.iterListNodeByWhile(deleteIndexSingleListNode);
    }
}