0079 单链表

  

 

import java.util.Stack;
/*
 * 链表
 * 1.链表是有序的列表，以结点的方式来存储
 * 2.每个结点包含data域和next域
 * 3.各个结点不一定是连续存储
 * 4.链表分为带头结点的链表和没有带头结点的链表，头结点不存放具体数据，只表示链表的头
 * 
 * 单链表的增删改查
 * 应用实例——使用带头结点的单向链表实现水浒英雄排名管理
 * 1.第一种添加方法：直接添加到链表的尾部
 *         1.先创建头结点，表示单链表的头
 *         2.每添加一个结点，直接加入到链表最后遍历
 *         3.通过一个辅助遍历，帮助遍历整个链表
 * 
 * 2.第二种添加方法：根据排名将英雄插入到指定位置（如果有这个排名，则插入失败）
 *         1.找到新添加结点的位置,通过辅助变量 temp指向新结点前一个结点，遍历
 *         2.新结点.next = temp.next
 *         3.temp.next = 新结点
 * 
 * 3.修改结点信息，根据no编号修改(修改no相当于添加)
 *         根据no，找到需要修改的结点，定义一个辅助变量temp
 * 
 * 4.删除结点
 *         1.定义一个辅助变量temp，temp指向删除结点的前一个结点
 *         2.temp.next = temp.next.next
 *         3.被删除的结点没有其他引用指向，被垃圾回收机制回收
 * 
 * 5.查找结点
 *         遍历，找到就返回true，反之false
 * 
 * 练习：
 * 1.求单链表的有效结点个数
 * 2.查找单链表中的倒数第k个结点
 * 3.单链表的反转
 * 4.从尾到头打印单链表
 * 5.合并两个有序单链表，合并后仍然有序
 */
public class LinkerList_ {
    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 hero5 = new HeroNode(5, "关胜", "大刀");
        HeroNode hero6 = new HeroNode(6, "林冲", "豹子头");
        HeroNode hero7 = new HeroNode(7, "秦明", "霹雳火");
        HeroNode hero8 = new HeroNode(8, "呼延灼", "双鞭");
        
        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //添加(方法一)
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);
        
        //添加（方法二）
        singleLinkedList.add02(hero5);
        singleLinkedList.add02(hero8);
        singleLinkedList.add02(hero6);
        singleLinkedList.add02(hero7);
        //显示
        singleLinkedList.list();
        
        //修改
        HeroNode newHeroNode = new HeroNode(1, "呼保义", "孝义黑三郎");
        singleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表");
        //显示
        singleLinkedList.list();
        
        //删除结点
        singleLinkedList.delete(1);
        singleLinkedList.delete(4);
        singleLinkedList.delete(8);
        System.out.println("删除后的链表");
        //显示
        singleLinkedList.list();
        
        //查找
        System.out.println("查找结果");
        System.out.println(singleLinkedList.search(1));
        System.out.println(singleLinkedList.search(2));
        System.out.println(singleLinkedList.search(3));
        
        //练习
        System.out.println("============================================================");
        //1.求单链表的有效结点个数
        System.out.println("有效结点个数=" + Test01.getLength(singleLinkedList.getHead()));
        //2.查找单链表中的倒数第k个结点
        HeroNode res = Test01.findIndexNode(singleLinkedList.getHead(),2);//倒数第二个
        System.out.println("倒数第二个结点=" + res);
        //3.单链表的反转
        System.out.println("单链表反转后=======================================");
        Test01.reversetList(singleLinkedList.getHead());
        singleLinkedList.list();
        //4.从尾到头打印单链表
        System.out.println("从尾到头打印单链表===================================");
        Test01.reversePrint(singleLinkedList.getHead());
        //5.合并两个有序单链表，合并后仍然有序
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList1.add02(hero2);
        singleLinkedList1.add02(hero3);
        singleLinkedList1.add02(hero5);
        singleLinkedList1.add02(hero6);
        singleLinkedList1.add02(hero7);
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.add02(hero1);
        singleLinkedList2.add02(hero4);
        singleLinkedList2.add02(hero8);
        System.out.println("第二个链表==============================================");
        singleLinkedList2.list();
        SingleLinkedList singleLinkedList3 = Test01.MergeList(singleLinkedList1, singleLinkedList2);
        System.out.println("两个链表合并后==========================================");
        singleLinkedList3.list();
    }
}
//定义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;//没有找到，将temp后移
        }
        //退出while循环时，temp就指向了链表的最后
        temp.next = heroNode;
    }
    
    //第二种添加方法：根据排名将英雄插入到指定位置（如果有这个排名，则插入失败）
    public void add02(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) {//说明编号存在
                flag = true;
                break;
            }
            temp=temp.next;//都不满足上述情况，将temp后移
        }
        //判断flag的值
        if (flag) {
            System.out.printf("编号%d已经存在，不能加入\n",heroNode.no);
        }else {
            //插入到链表中，即插入到temp后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
        
    }
    
    //修改结点信息，根据no编号修改(修改no相当于添加)
    public void update(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;
        }
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else {//没有找到
            System.out.printf("没有找到%d的结点，不能修改\n",newHeroNode.no);
        }
    }
    
    //删除结点
    public void delete(int no) {
        //定义一个辅助变量temp，temp指向删除结点的前一个结点
        HeroNode temp = head;
        boolean flag = false;//标志是否找到
        while(true) {
            if (temp.next == null) {//已到链表最后
                break;
            }
            if (temp.next.no == no) {//找到了要删除的结点
                flag = true;
                break;
            }
            temp = temp.next;//temp后移
        }
        if (flag) {
            temp.next = temp.next.next;
        }else {
            System.out.printf("要删除的%d结点不存在\n",no);
        }
    }
    
    //查找
    public boolean search(int no) {
        HeroNode temp = head.next;
        while(temp != null) {
            if (temp.no == no) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }
    
    
    //显示链表(遍历)
    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 + "]";
    }
}

class Test01 {
    //1.求单链表的有效结点个数(如果是带头结点，则不统计头结点)
    public static int getLength(HeroNode head) {//head为链表的头结点，返回有效个数
        if (head.next == null) {//空链表
            return 0;
        }
        int length = 0;
        //定义辅助变量
        HeroNode temp = head.next;
        while(temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }
    
    //2.查找单链表中的倒数第k个结点
    //        1.编写一个方法，接收head结点，同时接收一个index，index表示倒数第几个
    //        2.先把链表从头到尾遍历，得到链表的总长度
    //        3.得到size长度后，从链表的第一个开始，遍历（size-index）个
    //        4.如果找到返回该结点，否则返回null
    public static HeroNode findIndexNode(HeroNode head,int index) {
        //判断空
        if (head.next == null) {
            return null;
        }
        //第一次遍历，得到链表长度(结点个数)
        int size = getLength(head);
        //第二次遍历，遍历（size-index）个
        if (index <=0 || index > size) {//判断index是否合法
            return null;
        }
        //定义辅助变量,循环定位 倒数第index个
        HeroNode temp = head.next;
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }
        return temp;
    }
    
    //3.单链表的反转
    //        1.先定义一个结点reverseHead = new HeroNode();
    //        2.从头到尾遍历原链表，每遍历一个结点，就将其取出，并放在新的链表的最前端
    //        3.原来的链表head.next = reverseHead.next
    public static void reversetList(HeroNode head) {
        //如果链表为空，或只有一个结点，无需反转，直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义辅助指针
        HeroNode temp = head.next;
        HeroNode next = null;//指向当前结点（temp）的下一结点
        HeroNode reverseHead = new HeroNode(0,"","");
        //从头到尾遍历原链表，每遍历一个结点，就将其取出，并放在新的链表的最前端
        while(temp != null) {
            next = temp.next;//暂时保存当前结点的下一结点（保存）
            temp.next = reverseHead.next;//将temp下一结点指向新链表的下一结点（后连）
            reverseHead.next = temp;//将temp连接到新链表上（前连）
            temp = next;//temp后移
        }
        //将head.next指向reverseHead.next，完成反转
        head.next = reverseHead.next;
    }
    
    //4.从尾到头打印单链表
    //方式1：先将单链表反转，然后再遍历，但破坏了原来的单链表结构
    //方式2：利用栈（先进后出），将各个节点压入到栈中，利用先进后出实现逆序打印
    //stack.push()压入栈 stack.pop()出栈
    public static void reversePrint(HeroNode head) {
        if (head.next == null) {
            return;//空链表，不能打印
        }
        //创建一个栈
        Stack stack = new Stack();
        HeroNode temp = head.next;
        //将所有结点压入栈
        while(temp != null) {
            stack.push(temp);
            temp = temp.next;//后移
        }
        //将栈中的结点进行打印
        while(stack.size() > 0) {
            System.out.println(stack.pop());//先进后出
        }
    }
    
    
    //5.合并两个有序单链表，合并后仍然有序
    public static SingleLinkedList MergeList(SingleLinkedList singleLinkedList1,SingleLinkedList singleLinkedList2) {
        //创建一个新链表
        SingleLinkedList singleLinkedList3 = new SingleLinkedList();
        //定义辅助变量temp指向头结点的下一结点
        //定义辅助变量rear指向合并链表的最后一个位置
        //定义辅助变量next指向当前结点（temp）的下一结点
        HeroNode temp1 = singleLinkedList1.getHead().next;
        HeroNode temp2 = singleLinkedList2.getHead().next;
        HeroNode rear = singleLinkedList3.getHead();
        HeroNode next = null;
        //判断链表为空的情况
        if (temp1 == null && temp2 == null) {
            System.out.println("链表为空");
            return null;
        }
        //都不为空
        while(temp1 != null && temp2 != null) {
            if (temp1.no < temp2.no) {
                //添加较小的结点，即temp1
                next = temp1.next;//保存下一结点位置
                rear.next = temp1;//添加结点到新结点
                rear = rear.next;//rear后移
                temp1 = next;//temp1后移
            }else if (temp1.no > temp2.no) {//同上
                next = temp2.next;
                rear.next = temp2;
                rear = rear.next;
                temp2 = next;
            }else {//当有相同结点时，在前面的基础上移动另一链表的temp
                next = temp1.next;//保存下一结点位置
                rear.next = temp1;//添加结点到新结点
                rear = rear.next;//rear后移
                temp1 = next;//temp1后移
                temp2 = temp2.next;//temp2后移
            }
        }
        //添加剩余的链表
        if (temp1 == null) {
            rear.next = temp2;
        }else {
            rear.next = temp1;
        }
        return singleLinkedList3;
    }
    
}