Java-单向链表-从实现到各类操作（全家桶，包含各类常见方法）

package com.lixunhuan.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
public static void main(String[] args) {
    /**
     * 测试步骤：
     * 1）先创建几个节点
     * 2）创建一个链表
     * 3）节点连入链表中
     */

    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    HeroNode hero4 = new HeroNode(4, "公孙胜", "入云龙");

    SingleLinkedList singleLinkedList = new SingleLinkedList();
    //测试增加节点的方法
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero2);
    //测试 按序增加节点的方法
    singleLinkedList.addByOrder(hero1);
    singleLinkedList.addByOrder(hero3);
    singleLinkedList.addByOrder(hero4);
    singleLinkedList.addByOrder(hero2);
    singleLinkedList.addByOrder(hero2);//重复 会给出提示。
    singleLinkedList.list();
    System.out.println("*********************************************************");
    //测试修改节点的代码
    HeroNode newHeroNode = new HeroNode(2, "卢指导", "鲈鱼");
    singleLinkedList.update(newHeroNode);
    singleLinkedList.list();
    //测试删除指定节点的方法 测试了1，2，3，4，5均经过了考核
    System.out.println("*********************************************************");
    singleLinkedList.delete(4);
    singleLinkedList.list();
    System.out.println("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
    System.out.println(singleLinkedList.getLength(singleLinkedList.getHead()));
    System.out.println(singleLinkedList.findLastIndexNode(singleLinkedList.getHead(), 1).name);
    //测试单向链表逆序
    singleLinkedList.reverseList(singleLinkedList.getHead());
    singleLinkedList.list();
    //测试逆序打印（原链表不逆序）
    singleLinkedList.reversePrint(singleLinkedList.getHead());
}
}

/**
 * 定义一个SingleLinkedList
 */
class TestMergeList {
public static void main(String[] args) {
    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    HeroNode hero4 = new HeroNode(4, "公孙胜", "入云龙");
    HeroNode hero6 = new HeroNode(6, "林冲", "豹子头");

    SingleLinkedList singleLinkedList1 = new SingleLinkedList();
    SingleLinkedList singleLinkedList2 = new SingleLinkedList();
    singleLinkedList1.addByOrder(hero2);
    singleLinkedList1.addByOrder(hero4);
    singleLinkedList2.addByOrder(hero1);
    singleLinkedList2.addByOrder(hero3);
    singleLinkedList2.addByOrder(hero6);
    singleLinkedList1.list();
    System.out.println("--------------------分隔符1----------------------");
    singleLinkedList2.list();
    SingleLinkedList singleLinkedList3 = new SingleLinkedList();
    singleLinkedList3.mergeList(singleLinkedList1.getHead(), singleLinkedList2.getHead());
    System.out.println("--------------------分隔符2----------------------");
    singleLinkedList3.list();

}
}

class SingleLinkedList {
//先初始化一个头节点，头节点不能动,也不存放数据
private HeroNode head = new HeroNode(0, null, null);

public HeroNode getHead() {
    return head;
}

//编写添加新节点的方法。
// 不考虑英雄排名的思路：1）找到当前链表最后一个元素 2）使其next节点指向当前节点

public void add(HeroNode heroNode) {
    //因为头节点不能动，所以我们需要一个辅助遍历来遍历链表找到最后节点
    HeroNode temp = head;
    //while循环用来找到当前链表的尾部
    while (temp.next != null) {
        temp = temp.next;
    }
    //是最后节点指向新增节点
    temp.next = heroNode;
}

//考虑到排序的增加元素方法
public void addByOrder(HeroNode heroNode) {
    //因为头节点不能动，我们这里依然通过一个辅助变量来找到添加的位置
    //又由于是单向链表，所以temp是要位于添加位置的前一个节点，这样才插入合法
    HeroNode temp = head;
    boolean flag = false; // 标识添加的英雄是否则在，默认为false

    while (temp.next != null) {
        //虽然是单向链表，但是依据当前节点是可以写出下面任何一个位置的节点的相关属性，
        //比如temp.next.next.next.no
        if (temp.next.no > heroNode.no) {
            break;
        } else if (temp.next.no == heroNode.no) {
            flag = true;
            break;
        } else {
            temp = temp.next;
        }
    }
    if (flag) {
        System.out.printf("英雄:%d不要重复添加英雄\n", heroNode.no);
    } else {
        heroNode.next = temp.next;
        temp.next = heroNode;
    }
}

/**
 * 修改节点的信息，根据no编号来修改，即no编号不能改
 * 说明：
 * 1. 根据newHeroNode 的 no来修改
 * 2.默认链表未排序
 */

public void update(HeroNode newHeroNode) {
    //判断是否为空
    if (head.next == null) {
        System.out.println("链表为空！");
    } else {//找到需要修改的节点
        //先定义一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false;//表示是否找到该节点，默认为false
        while (temp != null) {
            if (temp.no == newHeroNode.no) {
                //找到了
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag来判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.printf("没有找到编号为：%d\n", newHeroNode.no);
        }
    }
}

/**
 * 删除节点的方法编写
 * 默认链表未排序
 * 根据排序no来进行英雄删除
 * 删除要查找的节点不再是对应no编号的节点，而是要找到其上一个节点，和修改不一样
 */
public void delete(int no) {
    //1)判断链表是否为空
    if (head.next == null) {
        System.out.println("是空链表，无英雄");
        return;
    }
    //2）创建临时指针进行链表的遍历、查找
    HeroNode temp = head;
    boolean flag = false;//用于记录是否已找到指定英雄

    while (temp.next != null) {
        if (temp.next.no == no) {
            flag = true;//表示找到了
            break;
        } else if (temp.no == no) {
            flag = true;
            break;
        } else {
            temp = temp.next;
        }
    }
    if (flag) {
        temp.next = temp.next.next;
    } else {
        System.out.printf("未找到编号为：%d节点!\n", no);
    }
}

/**
 * 编写 遍历显示链表的方法
 */
public void list() {
    if (head.next == null) {
        System.out.println("链表为空!");
    } else {
        //因为头节点不能动，所以我们需要一个辅助遍历来遍历链表
        HeroNode temp = head.next;//这次遍历的时候可不需要头节点了，因为头节点不存有效数据
        while (temp != null) {
            System.out.println(temp);//即调用了重写的System.out.println(temp.toString());
            temp = temp.next;
        }
    }
}

/**
 * 编写得到链表长度的方法
 * 传入一个头节点（但不将其计入有效节点个数统计）
 */

public int getLength(HeroNode head) {
    if (head.next == null || head == null) {
        return 0;
    }
    int length = 0;
    HeroNode cur = head.next;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    return length;
}

/**
 * 查找单链表中的倒数第K个节点【新浪面试题】
 * 接收：head节点，index(倒数第index个节点)
 * 返回：找到则返回对应节点，没找到则返回null
 * 思路：受于单向链表限制，1）先遍历链表得到链表长度，2）然后得到正向看过去的节点数
 * 具体计算请见代码
 */
public HeroNode findLastIndexNode(HeroNode head, int index) {
    if (index <= 0)
        throw new RuntimeException("数组索引不合法\n");
    if (head == null || head.next == null) {
        return null;
    }
    int length = this.getLength(head);
    if (length < index)
        throw new RuntimeException("数组索引超出范围\n");
    int cishu = length - index;
    HeroNode cur = head.next;
    for (int i = 0; i < cishu; i++) {
        cur = cur.next;
    }
    return cur;
}

/**
 * 将单链表进行反转的方法
 */
public void reverseList(HeroNode head) {
    //先判断链表是否为空，是否只有一个节点，那么就无需反转，直接返回
    if (head.next == null || head.next.next == null)
        return;

    HeroNode cur = head.next;//定义一个辅助的指针，帮助遍历
    HeroNode next = null; //用于记录当前节点下一个节点
    HeroNode reverseHead = new HeroNode(0, "", "");

    //遍历原来的链表，并从头开始遍历原来链表，每遍历一个节点，就将其取出，并放在新链表最前端（reverseHead.next处）
    while (cur != null) {
        next = cur.next;
        cur.next = reverseHead.next;
        reverseHead.next = cur;
        cur = next;
    }
    head.next = reverseHead.next;//这一步很关键，头部和反转头部的交接工作！别落下！
}

/**
 * 反序输出一个单向链表的方法，且原链表结构保持不变
 *
 * @param head
 */
public void reversePrint(HeroNode head) {
    if (head.next == null)
        return;
    //创建一个栈，将各个节点压入栈中
    Stack<HeroNode> stack = new Stack<>();
    HeroNode cur = head.next;
    //将链表的所有节点压入
    // 栈中
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;//这样就可以压入下一个节点
    }
    //将栈中的节点进行打印

    while (stack.size() > 0) {
        System.out.println(stack.pop());
    }
}

/**
 * 连接两个有序单向链表的方法
 * 排序依据：将的 no序号进行升序排序 （当然，原本要合并的序列也是这样排好序的）
 */
public void mergeList(HeroNode head1, HeroNode head2) {
    if (head1.next == null) {
        System.out.println("无需合并");
        head = head2;
    }
    if (head2.next == null) {
        System.out.println("无需合并");
        head = head1;
    }
    HeroNode cur1 = head1.next;
    HeroNode cur2 = head2.next;
    HeroNode mergeHead = new HeroNode(0, "", "");//头是不能变的，即不能再次被赋值
    HeroNode mergeCur = mergeHead;
    while (cur1 != null && cur2 != null) {
        if (cur1.no < cur2.no) {
            mergeCur.next = cur1;
            cur1 = cur1.next;//队列向后移动一个节点
            mergeCur=mergeCur.next;//新链表
        } else if (cur1.no == cur2.no) {
            mergeCur.next = cur1;
            cur1 = cur1.next;
            cur2 = cur2.next;
            mergeCur=mergeCur.next;
        } else {
            mergeCur.next = cur2;
            cur2 = cur2.next;
            mergeCur=mergeCur.next;
        }
    }
    if (cur1 == null && cur2 != null) {
        mergeCur.next = cur2;
    }
    if (cur2 == null && cur1 != null) {
        mergeCur.next = cur1;
    }
    head = mergeHead;
}
}
/**
* 定义一个将节点
*/
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next;//指向下一个节点

//构造器，注意单向链表新增节点的时候，其是不知道下一个节点的指向的，要么不管，要么赋值null

public HeroNode(int no, String name, String nickname) {
    this.no = no;
    this.name = name;
    this.nickname = nickname;
    this.next = null;
}

//为了显示方便 重写toString方法

@Override
public String toString() {
    return "HeroNode{" +
            "no=" + no +
            ", name='" + name + '\'' +
            ", nickname='" + nickname + '\'' +
            '}';
}
}