数据结构与算法之链表

文章目录

- - 链表
  - - 单链表完成添加的遍历
    - 按照顺序添加英雄
    - - 解题思路：
      - 代码实现：
    - 单链表的修改
    - - 解题思路：
      - 代码实现：
    - 单链表的删除：
    - - 解题思路：
      - 代码实现：
  - 实战演练
  - - 找出单链表中有效节点的个数
    - 查找单链表倒数第K个节点[新浪面试]
    - - 解题思路：
    - 单链表的反转：
    - - 解题思路：
      - 代码实现：
    - 从尾到头打印单链表[百度]
    - - 解题思路：
  - 双向链表
  - - 解题思路：
    - 双向链表的创建(多了pre)
    - 双线链表的添加
    - 双向链表的修改
    - 双链表的删除
  - 单向环形链表
  - - 创建节点起始结构
    - 构建
    - 遍历环形链表
    - 解决约瑟夫环
    - - 思路分析：
      - 代码实现：

1.应用场景
2.数据结构的算法
3.原理剖析
4.分析实验步骤
5.代码实现

链表单链表完成添加的遍历

package linkedList;
class HeroNode{
    //编号
    public int no;
    //名字
    public String name;
    //昵称
    public String niceName;
    //指针指向后面
    public HeroNode next;

    public HeroNode(int no, String name, String niceName) {
        this.no = no;
        this.name = name;
        this.niceName = niceName;
    }

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

//再次定义一个单链表
class MylinkedList{
    //定义一个头结点
    private HeroNode head = new HeroNode(0,"","");

    //添加节点到单链表
    
    public  void add(HeroNode heroNode){
        //需要创建一个临时的temp来替代head
        HeroNode temp = head;
        while (true){
            //这个next算是节点里面的属性，节点里面还有一个属性节点
            if (temp.next==null){
                 break;
            }
            //如果不是，就把temp后移
               temp = temp.next;
        }
        //从上面出来的时候也代表节点指向最后
        temp.next = heroNode;
    }

    //遍历这个链表
    public void list(){
        //需要先判断头结点是否为空
        if (head.next ==null){
            System.out.println("链表为空");
            return;
        }
        //需要判断是否到达尾节点，如果没有到达就输出并指针后移并输出节点位置
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }else {

                System.out.println("节点位置为"+temp);
                temp = temp.next;
            }
        }
    }
}

public class SinglelinkedList {
    //在链表尾部加入英雄

    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,"林冲","豹子头");

        MylinkedList linkedList = new MylinkedList();
        linkedList.add(hero4);
        linkedList.add(hero1);
        linkedList.add(hero2);
        linkedList.add(hero3);

        linkedList.list();
    }

}

按照顺序添加英雄解题思路：

1.通过遍历找到节点，并从该节点处做一个辅助节点temp
2.该节点的next指向temp的next
3.temp.next指向该节点

代码实现：

 //按照顺序添加
    public void addOrderBy(HeroNode heroNode){
        HeroNode temp  = head;
        //设置标志位,刚开始为false,用来判断是否重复的
        boolean flag = false;

        //然后通过变量来找到需要插入的位置
        while (true){
            if (temp.next==null){
                //如果只有头结点，那么就返回，因为不存在重复的
                break;
            }
            //如果temp当前的编号，大于节点的编号，那就说明已经过了，就说明需要在temp的后面添加
            //因为temp是从前往后推的，所以只能出现temp heroNode.no){
                break;
            }else if (temp.next.no == heroNode.no){
                //如果相等就说明重复了
                flag = true;//说明编号存在
                break;
            }
            //temp是从前往后推的
            temp = temp.next;
       }
        if (flag == true){
            System.out.println("需要插入的节点和列表节点重复"+heroNode.no);
        }else {
            //正式因为这两步才将链表插入在中间
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

单链表的修改解题思路：

1.判断链表是否为空
2.创建辅助节点，设置标志位
2.进入循环，判断链表是否遍历到最后，如果不是指针后移
4.判断标志位是否为1，是则修改

            temp.name = newHeroNode.name;
            temp.niceName = newHeroNode.niceName;

代码实现：

//修改节点的信息
    //1.根据newHeroNode的no来修改
    public void update(HeroNode newHeroNode){
        //判断判断除了头结点外是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点
        //遍历所有节点，找到需要修改的节点
        //需要做辅助节点
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            if (temp == null){
                System.out.println("说明已经遍历完了链表");
            }
            //如果没有遍历完成，就开始找和修改匹配的情况
            if (temp.no == newHeroNode.no){
                flag = true;
                break;
            }

            //如果没找到就往后遍历
            temp = temp.next;
            //如果真到了最后一个位final
            //这里是如果temp不为空，就把temp的

        }
        if (flag == true){
            //如果找到这个位置，就对这个位置的昵称的名字进行修改
            temp.name = newHeroNode.name;
            temp.niceName = newHeroNode.niceName;
        }else {
            //没有找到
            System.out.println("没有找到编号是这个的节点"+newHeroNode.no);
        }
    }
       //创建节点
//        Heronode newHeronode = new Heronode(4,"零充","豹子头");
//        linkedList.update(newHeroNode);
//        linkedList.list();

单链表的删除：解题思路：

1.判断链表是否为空
2.设置标志位，设置辅助节点
3.进入循环，判断temp.next.no 是否等于参数no,如果是标志位置1，如果不是指针后移
4.判断标志位状态，为1就将当前指针指向下个指针

代码实现：

//删除方法    
public void delete(int no){
        if (head.next==null){
            System.out.println("链表为空链表");
            return;
        }
        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 == true){
            //将temp的next指针指向temp指针的下一个指针
            temp.next = temp.next.next;
        }

    }

//调用
        String a = "----------------------------------";
        //删除节点
        linkedList.delete(5);
        System.out.println(a);
        System.out.println("删除后的链表情况");
        linkedList.list();
        linkedList.delete(2);
        System.out.println(a);
        System.out.println("删除后的链表情况");
        linkedList.list();
        linkedList.delete(3);
        linkedList.delete(1);
        linkedList.delete(4);
        System.out.println(a);
        System.out.println("删除后的链表情况");
        linkedList.list();

实战演练找出单链表中有效节点的个数

 public   int Valid(HeroNode heroNode){
        if (head.next == null){
            //如果是这样就返回一个空链表
            return  0;
        }
        //这里没有统计头结点
        HeroNode temp = head.next;
        int length = 0;
          
            while (temp !=null){
                length++;
                temp = temp.next;
            }
            return  length;
        }
    }
//这里需要获取头结点，需要获取一个getHead方法
    //统计除头结点外其他节点的个数
        System.out.println(a);
        System.out.println("有效节点为");
        System.out.println(linkedList.Valid(linkedList.getHead()));

查找单链表倒数第K个节点[新浪面试] 解题思路：

1.设置一个方法接收head以及一个参数index
2.index表示是倒数第index节点
3.先把链表从头到尾遍历，得到链表长度getLength
4.得到size后，我们从链表遍历size-length个
5如果找到了返回节点，找不到返回为null

 public static HeroNode findLastIndexNode(HeroNode head, int index) {
        if (head.next == null) {
            return null; //没有找到
        }
        //找到size的长度
        int size = Valid(head);
        //如果下标越界的话，也是没有找到
        if (index <= 0 || index > size) {
            //这个也是没有找到
            return null;
        }
        //然后做一个辅助节点,定位到倒数第几个节点
        HeroNode temp = head.next;
        for (int i = 0; i  
单链表的反转： 
解题思路： 
1.先定义一个节点reverseNode = new Heronode();
2.遍历原来链表，编列节点，放在链表最前端
3.原来的链表head.next = reverseNode.next 
代码实现： 

  
前面的是指针，后面是指针指向的数据 
   public static void reserseList(HeroNode head){
       //如果当前链表为空，或只有一个节点，无需反转直接返回
       if (head.next == null|| head.next.next == null){
           return;
       }
       //定义一个辅助指针,帮我们遍历链表
       HeroNode cur = head.next;
       HeroNode next = null;
       HeroNode reverseHead = new HeroNode(0,"","");
       //遍历原来的链表,每遍历一个结点，就取出，让后放在reverseHead最前面
       while (cur != null){
            next = cur.next;   //首先把cur.next储存起来之后要用
            cur.next = reverseHead.next;  //将reverseHead.next以后的拼接到cur上面
            reverseHead.next = cur;      //给reverseHead.next赋值，顺便放在第一位
            cur = next;                  //将现在的cur.next也就是next赋给cur也就是指针后移
       }

       //将head.next指向reverseHead.next实现单链表反转（等于说将head.next拼接上已经反转好的reverseHead.next）
       head.next = reverseHead.next;
       System.out.println();
   }
 
从尾到头打印单链表[百度] 
解题思路： 
1.上面题就是要逆序打印大连表
2.方式一：反转再打印，这会破坏单链表结构
3.方式二：将数据压入栈中然后利用栈的先进后出，就实现逆序 
    public static void reversePrint(HeroNode head){
        if (head.next == null){
            return;
        }
        //需要设置辅助节点
        HeroNode temp = head.next;
        Stack heronodes = new Stack<>();
        while (temp != null){
//            temp不为空则压入栈中
              heroNodes.push(temp);
              temp = temp.next;
        }
        while(!heroNodes.empty()){
            System.out.println(heroNodes.pop());
        }
    }
 
双向链表 
解题思路： 
1.遍历方式和单链表一样，可以向前查找也可以向后查找
2.添加（默认加在双向链表的最后）
 
  先找到双向链表最后的这个结点
temp.next = new HeroNode;
new Heronode.pre = temp ;
 
3.修改思路和单链表一样
4.删除
 
  因为是双向链表，因此我们可以实现自我删除
temp.pre.next = temp .next;
temp.next.pre = temp. pre;
  
双向链表的创建(多了pre) 
class HeroNode2 {
    //编号
    public int no;
    //名字
    public String name;
    //昵称
    public String niceName;
    //指针指向后面
    public HeroNode2 next;  //指向下一个节点

    public HeroNode2 pre;   //指向前一个节点

    public HeroNode2(int no, String name, String niceName) {
        this.no = no;
        this.name = name;
        this.niceName = niceName;
    }

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

 
双线链表的添加 
 temp.next = heroNode;
 heroNode.pre = temp;
 
双向链表的修改 
//较之前的没啥区别
 
双链表的删除 
双链表的删除不用使用删除节点前面的节点了，所以修改还是比较大的 
 public void delete(int no) {
        if (head.next == null) {
            System.out.println("链表为空链表");
            return;
        }
    //原来为head
        HeroNode2 temp = head.next;
        boolean flag = false;
        while (true) {
          //这里就直接用temp而不是temp.next
            if (temp == null) {
                break;
            }
            if (temp.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag == true) {
          //这里也是修改了
            temp.pre.next= temp.next;
            //如果是最后一个特节点就不需要执行下面这句话
            temp.next.pre = temp.pre;

        }

    }
 
单向环形链表 
创建节点起始结构 
//创建一个Boy，表示一个节点
class Boy {
    private int no; //编号
    private Boy next; // 指向下一个节点，默认为null

    public void setNo(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public Boy(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}
 
构建 
创建第一个节点，让first指向该节点，形成环形
创建一个新节点，把节点加入这个新的环形链表 
  public void addBoy(int nums) {
        //nums做一个数据校验
        if (nums < 2) {
            System.out.println("num值不正确 ");
        }
        Boy curBoy = null;
        //for循环创建链表

        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                //1.设置自己为第一个节点
                first = boy;
                //2.将自己组成环
                first.setNext(first);
                //3.讲辅助节点设置为当前
                curBoy = first;
            } else {
                //否则就是之后的节点了，就开始解环，组环
                
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
 
遍历环形链表 
1.先让一个辅助指针curBoy,指向first节点 
2.然后通过while遍历环形链表即可curBoy.next== first结束 
    public void showBoy() {
        if (first == null) {
            System.out.println("节点为空");
        }
        //设置辅助指针
        Boy curBoy = first;
        while (true) {
            System.out.println("这是第" + curBoy.getNo() + "个节点");
            //判断遍历完毕条件
            if (curBoy.getNext() == first) {
                break;
            }
            //否则就继续遍历
            curBoy = curBoy.getNext();
        }
    }
 
解决约瑟夫环 
思路分析： 
 
代码实现： 
    
    public void CountBoy(int startNo, int countNum, int nums) {
        //首先对传入的数字进行校验
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数有误，请校验后再继续执行");
        }
        //然后设置辅助节点helper,我们需要把helper放在对位，以便于删链
        Boy helper = first;
        while (true) {
            //这个操作是将helper放在最后一位
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }

        //然后我们需要在报数之前移动startNo - 1 次
        for (int i = 0; i < startNo - 1; i++) {
            helper = helper.getNext();
            first = first.getNext();
        }
        int count = 0;
        while (true){
            if (helper == first){
                break;
            }
            for (int j = 0; j < countNum - 1; j++) {
                helper = helper.getNext();
                first = first.getNext();
            }
            count++;
            //然后将节点取消
            System.out.println("第"+count+"轮出圈的小孩为"+first.getNo());
            //将first往后推，然后将helper指向first
            first = first.getNext();
            helper.setNext(first) ;
        }
        System.out.println("最后一个留在圈中的小孩为"+first.getNo());

    }

数据结构与算法之链表

Java相关栏目本月热门文章