SingleLinkList

单链表基础功能
数据结构——初始单链表

增删改查

//定义SingleLinkedList管理英雄
class SingleLinkedList {
    //先初始化一个头节点,头节点不要动，不存放具体数据
    private HeroNode head = new HeroNode ( 0, "", "" );

    //返回头节点
    public HeroNode getHead ( ) {
        return head;
    }

    //添加节点到单链表中
    //思路，当不考虑编号顺序时，
//        1.找到链表最后一个节点
//        2.将最后这个节点的next指向新节点
    public void add ( HeroNode heroNode ) {
        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表找到最后
        while (true) {
            //找到链表的最后
            if ( temp.next == null ) {
                break;
            }
            temp = temp.next;
        }
        //当退出while时，temp就指向最后
        temp.next = heroNode;
    }

    //第二种方式在添加英雄，将英雄添加到指定位置
    //如果有这个排名提示添加失败
    public void addpro ( HeroNode heroNode ) {
        //因为头节点不能动，因此仍需要辅助节点来帮助我们添加
//        因为单链表,因此我们找的temp是位于添加位置的前一个节点，否则添加不进去
        HeroNode temp = head;
        boolean flag = false; //标志添加的编号是否存在，默认为false
        while (true) {
            if ( temp.next == null ) {//说明temp已经在链表最后
                break;
            }
            if ( temp.next.no > heroNode.no ) {//位置找到，就在temp后面插入
                break;
            }
            else if ( temp.next.no == heroNode.no ) {//要添加的heronode依然存在
                flag = true;
                break;
            }
            temp = temp.next;//后移遍历
        }
        if ( flag ) {//编号存在
            System.out.printf ( "准备插入的英雄编号%d,已经存在,不能加入\n", heroNode.no );
        }
        else {
            //插入到正确位置。temp后面
            heroNode.next = temp.next;
            temp.next     = heroNode;
        }

    }

    //修改节点的信息，根据no来修改，name，nickname
    public void updata ( HeroNode newHeroNode ) {
        //判断是否为空
        if ( head.next == null ) {
            System.out.println ( "链表为空" );
            return;
        }
        //找到需要修改的节点，根据no编号
        HeroNode temp = head.next;
        boolean flag = false;//表示是否找到该节点
        while (true) {
            if ( temp == null ) {
                break;  //链表已经遍历完
            }
            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 );
        }
    }

    //删除节点
    //就是将要删除的前一个节点的next==要删除的next
//    temp.next=temp.next.next;
    //思路：
    //1.head不能动，因此我们需要一个temp辅助接点找到待删除的前一个节点
    //2.说明我们在比较时，temp.next.no=目标节点的no
    public void delete ( int no ) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if ( temp.next == null ) {
                break;
            }
            if ( temp.next.no == no ) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if ( flag ) {
            temp.next = temp.next.next;
        }
        else {
            System.out.printf ( "列表中的no值无%d,无法删除\n", no );
        }
    }

    //查找
    public void find ( int no ) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if ( temp.next == null ) {
                break;
            }
            if ( temp.no == no ) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if ( flag ) {
            System.out.println ( "你查找的信息如下：" );
            System.out.println ( temp );
        }
        else {
            System.out.printf ( "列表中的no值无%d,无法查到\n", no );
        }
    }

    //显示链表遍历
    public void list ( ) {
        //判断链表是否为空
        if ( head.next == null ) {
            System.out.println ( "链表为空" );
            return;
        }
        //因为头节点，不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if ( temp == null ) {
                break;
            }
            //输出节点的信息
            System.out.println ( temp );
            //将temp后移
            temp = temp.next;
        }

    }


}

//定义一个heroNode,每个HeroNode 对象是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;

    //构造器
    public HeroNode ( int no, String name, String nickname ) {
        this.no       = no;
        this.name     = name;
        this.nickname = nickname;
    }

    //为了显示方便，我们重写toString
    @Override
    public String toString ( ) {
        return "HeroNode [no=" + no + ",name=" + name + ",nickname=" + nickname + "]";
    }
}

测试

public class SingleLinkListDemo {
    public static void main ( String[] args ) {
        //进行一个测试
        //先创建节点
        HeroNode hero1 = new HeroNode ( 1, "松江", "及时雨" );
        HeroNode hero2 = new HeroNode ( 3, "卢俊义", "玉麒麟" );
        HeroNode hero3 = new HeroNode ( 2, "吴用", "智多星" );
        HeroNode hero4 = new HeroNode ( 4, "林冲", "豹子头" );

        //创建一个链表
        SingleLinkedList singleLinkedList1 = new SingleLinkedList ( );

        //加入
//        singleLinkedList1.add ( hero1 );
//        singleLinkedList1.add ( hero2 );
//        singleLinkedList1.add ( hero3 );
//        singleLinkedList1.add ( hero4 );

//        System.out.println ("增删改查" );
        //添加
        singleLinkedList1.addpro ( hero1 );
        singleLinkedList1.addpro ( hero3 );
        singleLinkedList1.addpro ( hero2 );
        singleLinkedList1.addpro ( hero2 );
        singleLinkedList1.addpro ( hero4 );

        singleLinkedList1.list ( );

        //修改
        HeroNode newHeroNode = new HeroNode ( 2, "小卢", "玉麒麟~~" );
        singleLinkedList1.updata ( newHeroNode );
        //显示列表
        singleLinkedList1.list ( );

        //查找
        singleLinkedList1.find ( 3 );

        //删除
        singleLinkedList1.delete ( 1 );
        singleLinkedList1.delete ( 4 );
        System.out.println ("删除完后的列表" );
        singleLinkedList1.list ( );
        System.out.printf ("链表中有效节点为%d\n",getLength ( singleLinkedList1.getHead()));
    }
}

单链表题目练习

求链表的有效节点个数

//方法：获取到单链表的有效节点个数（如果是带头节点的列表，需要去掉头）

/**
 * @param head 链表的头节点
 * @return 返回值为有效值的个数
 */
public static int getLength ( HeroNode head ) {
    if ( head.next == null ) {//空列表
        return 0;
    }
    int length = 0;
    //定义一个辅助节点,这里我们没有统计头节点
    HeroNode temp = head.next;
    while (temp != null) {
        length++;
        temp = temp.next;//遍历
    }
    return length;
}

查找单链表的倒数第K个节点

//查找单链表的倒数第K个节点
//思路
//1.编写一个方法，接收一个head节点，同时接收一个index(index为查找倒数第几个的值)
//2.先把链表从头到位遍历，先得到总的长度
//3.然后遍历从头到（size-index）个
public static void findIndex ( HeroNode head, int index ) {
    if ( head.next == null ) {
        System.out.println ( "列表为空" );
    }
    int size = getLength ( head );
    int num = size - index;
    if ( num < 0 || num > size ) {
        System.out.println ( "index值输入错误" );
        return;
    }
    int i = 0;
    HeroNode temp = head.next;
    while (i < num) {
        i++;
        temp = temp.next;
    }
    System.out.println ( temp );

}

单链表进行反转

    //单链表进行反转
    public static void reverseLinkedList ( HeroNode head ) {
        //如果当前列表为空，或者只有一个节点，就不去反转，直接返回
        if ( head.next == null || head.next.next == null ) {
            return;
        }

        //定义一个辅助指针，帮助我们遍历原来的链表
        HeroNode temp = head.next;
        HeroNode next = null; //指向当前节点的下一个节点
        HeroNode reverseHead = new HeroNode ( 0, "", "" );
        //遍历原来的链表，
        //并且每遍历一个节点，就将其取出，并放到新的列表reverseHead的最前端
        while (temp != null) {
            //让辅助链表替原链表遍历，让节点的下一个等于新链表head.next
            next      = temp.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
            temp.next = reverseHead.next;  //解决后连问题  把原链表的节点的next数据清除，达到一次插入一个节点
//            System.out.println (reverseHead.next );
            reverseHead.next = temp;  //解决头部与遍历节点的连接
            temp             = next;
        }
        //将head.next指向reverseHead.next，实现单链表反转
        head.next = reverseHead.next;
    }

逆序打印单链表

//从尾到头打印单链表（逆序打印单链表）
//可以利用栈这个数据结构，将各个节点压入栈中，再利用栈的先进后出的特点，实现逆序打印
public static void reversePrint ( HeroNode head ) {
    if ( head.next == null ) {
        System.out.println ( "空链表无打印" );
        return;
    }
    //创建一个栈，将各个节点压入栈中
    Stack<HeroNode> stack = new Stack<HeroNode> ( );
    HeroNode temp = head.next;
    //将链表的所有结点压入站点
    while (temp != null) {
        stack.push ( temp );  //压入
        temp = temp.next;
    }
    //压入栈以后，将栈中的节点进行打印
    while (stack.size ( ) > 0) {
        System.out.println ( stack.pop ( ) );  //弹出
    }
}

合并两个有序的单链表，合并之后依然有序

//合并两个有序的单链表，合并之后依然有序
public static SingleLinkedList combineSingleLink ( SingleLinkedList link1, SingleLinkedList link2 ) {
    HeroNode head1 = link1.getHead ( );
    HeroNode head2 = link2.getHead ( );
    if ( head1.next == null && head2.next == null ) {
        return null;
    }
    if ( head1.next == null ) {
        System.out.println ( "链表一为空" );
        return link2;
    }
    if ( head2.next == null ) {
        System.out.println ( "链表二为空" );
        return link1;
    }

    HeroNode temp1 = head1.next;
    HeroNode temp2 = head2.next;
    SingleLinkedList link = new SingleLinkedList ( );
    HeroNode temp = link.getHead ( );
    temp.next = temp1;
    HeroNode next = null;
    while (temp2 != null) {
        if ( temp.next == null ) {
            temp.next = temp2;
            break;
        }
        if ( temp2.no <= temp.next.no ) {
            next       = temp2.next;   //此部分和反转链表一样，这个要加在最后面，而反转链表反之
            temp2.next = temp.next;
            temp.next  = temp2;
            temp2      = next;
        }
        temp = temp.next;
    }
    return link;

}

测试2

public class SingleLinkListDemo {
    public static void main ( String[] args ) {
        //进行一个测试
        //先创建节点
        HeroNode hero1 = new HeroNode ( 2, "松江", "及时雨" );
        HeroNode hero2 = new HeroNode ( 3, "卢俊义", "玉麒麟" );
        HeroNode hero3 = new HeroNode ( 5, "吴用", "智多星" );
        HeroNode hero4 = new HeroNode ( 6, "林冲", "豹子头" );
        HeroNode hero5 = new HeroNode ( 1, "松江", "及时雨" );
        HeroNode hero6 = new HeroNode ( 4, "卢俊义", "玉麒麟" );
        HeroNode hero7 = new HeroNode ( 8, "吴用", "智多星" );
        HeroNode hero8 = new HeroNode ( 9, "林冲", "豹子头" );


        //创建一个链表
        SingleLinkedList singleLinkedList1 = new SingleLinkedList ( );
        SingleLinkedList singleLinkedList2 = new SingleLinkedList ( );

		//填充链表1和链表2
        singleLinkedList1.addpro ( hero1 );
        singleLinkedList1.addpro ( hero3 );
        singleLinkedList1.addpro ( hero2 );
        singleLinkedList1.addpro ( hero4 );
        singleLinkedList2.addpro ( hero5 );
        singleLinkedList2.addpro ( hero6 );
        singleLinkedList2.addpro ( hero7 );
        singleLinkedList2.addpro ( hero8 );
		
        //组合后的链表
        combineSingleLink ( singleLinkedList1, singleLinkedList2 ).list ( );

        System.out.printf ( "链表中有效节点为%d\n", getLength ( singleLinkedList1.getHead ( ) ) );
        //逆序打印
        System.out.println ( "测试逆序打印单链表,没有改变本身结构" );
        reversePrint ( singleLinkedList1.getHead ( ) );
        //查找倒数第二个值
        System.out.println ( "查找值" );
        findIndex ( singleLinkedList1.getHead ( ), 2 );
        System.out.println ( "修改之后的列表" );
        singleLinkedList1.list ( );
        //反转单链表
        System.out.println ( "原来链表" );
        singleLinkedList1.list ( );

        System.out.println ( "反转后的链表" );
        reverseLinkedList ( singleLinkedList1.getHead ( ) );
        singleLinkedList1.list ( );

    }

    //方法：获取到单链表的有效节点个数（如果是带头节点的列表，需要去掉头）

    /**
     * @param head 链表的头节点
     * @return 返回值为有效值的个数
     */
    public static int getLength ( HeroNode head ) {
        if ( head.next == null ) {//空列表
            return 0;
        }
        int length = 0;
        //定义一个辅助节点,这里我们没有统计头节点
        HeroNode temp = head.next;
        while (temp != null) {
            length++;
            temp = temp.next;//遍历
        }
        return length;
    }


    //查找单链表的倒数第K个节点
    //思路
    //1.编写一个方法，接收一个head节点，同时接收一个index(index为查找倒数第几个的值)
    //2.先把链表从头到位遍历，先得到总的长度
    //3.然后遍历从头到（size-index）个
    public static void findIndex ( HeroNode head, int index ) {
        if ( head.next == null ) {
            System.out.println ( "列表为空" );
        }
        int size = getLength ( head );
        int num = size - index;
        if ( num < 0 || num > size ) {
            System.out.println ( "index值输入错误" );
            return;
        }
        int i = 0;
        HeroNode temp = head.next;
        while (i < num) {
            i++;
            temp = temp.next;
        }
        System.out.println ( temp );

    }

    //单链表进行反转
    public static void reverseLinkedList ( HeroNode head ) {
        //如果当前列表为空，或者只有一个节点，就不去反转，直接返回
        if ( head.next == null || head.next.next == null ) {
            return;
        }

        //定义一个辅助指针，帮助我们遍历原来的链表
        HeroNode temp = head.next;
        HeroNode next = null; //指向当前节点的下一个节点
        HeroNode reverseHead = new HeroNode ( 0, "", "" );
        //遍历原来的链表，
        //并且每遍历一个节点，就将其取出，并放到新的列表reverseHead的最前端
        while (temp != null) {
            //让辅助链表替原链表遍历，让节点的下一个等于新链表head.next
            next      = temp.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
            temp.next = reverseHead.next;  //解决后连问题  把原链表的节点的next数据清除，达到一次插入一个节点
//            System.out.println (reverseHead.next );
            reverseHead.next = temp;  //解决头部与遍历节点的连接
            temp             = next;
        }
        //将head.next指向reverseHead.next，实现单链表反转
        head.next = reverseHead.next;
    }

    //从尾到头打印单链表（逆序打印单链表）
    //可以利用栈这个数据结构，将各个节点压入栈中，再利用栈的先进后出的特点，实现逆序打印
    public static void reversePrint ( HeroNode head ) {
        if ( head.next == null ) {
            System.out.println ( "空链表无打印" );
            return;
        }
        //创建一个栈，将各个节点压入栈中
        Stack<HeroNode> stack = new Stack<HeroNode> ( );
        HeroNode temp = head.next;
        //将链表的所有结点压入站点
        while (temp != null) {
            stack.push ( temp );  //压入
            temp = temp.next;
        }
        //压入栈以后，将栈中的节点进行打印
        while (stack.size ( ) > 0) {
            System.out.println ( stack.pop ( ) );  //弹出
        }
    }

    //合并两个有序的单链表，合并之后依然有序
    public static SingleLinkedList combineSingleLink ( SingleLinkedList link1, SingleLinkedList link2 ) {
        HeroNode head1 = link1.getHead ( );
        HeroNode head2 = link2.getHead ( );
        if ( head1.next == null && head2.next == null ) {
            return null;
        }
        if ( head1.next == null ) {
            System.out.println ( "链表一为空" );
            return link2;
        }
        if ( head2.next == null ) {
            System.out.println ( "链表二为空" );
            return link1;
        }

        HeroNode temp1 = head1.next;
        HeroNode temp2 = head2.next;
        SingleLinkedList link = new SingleLinkedList ( );
        HeroNode temp = link.getHead ( );
        temp.next = temp1;
        HeroNode next = null;
        while (temp2 != null) {
            if ( temp.next == null ) {
                temp.next = temp2;
                break;
            }
            if ( temp2.no <= temp.next.no ) {
                next       = temp2.next;
                temp2.next = temp.next;
                temp.next  = temp2;
                temp2      = next;
            }
            temp = temp.next;
        }
        return link;

    }
}