[数据结构与算法]数据结构与算法Day02链表

一、单向链表

单向链表是典型的链式存储结构，它是通过其中的节点两两相连形成的

思路分析：

需要有一个节点类来存储数据以及连接点

（1）创建Node类，其中注入一个Node next用来连接其他节点，其余属性为需要存储的数据

（2）创建SingleList类来管理Node节点，需要一个Node head头节点来进行链表查找，head头节点始终不能被改变，因为要保证头节点位置才能保证每次都可以遍历完全

1.实现节点类

public class Node {
    //三个属性用于存储数据
    private int i;
    private String name;
    private String sex;
    //Node属性用于连接各个节点
    private Node next;

    public Node(int i, String name, String sex) {
        this.i = i;
        this.name = name;
        this.sex = sex;
    }
}

2.实现链表类来管理节点

public class SingleLinkedList {
    //不可变的头节点，用于遍历链表
    private Node head = new Node(0,"","");
}

3.在链表类中加入add方法与list方法，用于添加数据与遍历数据

//添加节点进链表
    public void add(Node node){
        //需要一个临时变量存储head信息来进行遍历
        Node temp = head;
        //while循环用于找到最后一个节点的位置
        while (true){
            if(temp.getNext() == null){
                temp.setNext(node);
                break;
            }
            temp = temp.getNext();
        }
    }

//遍历链表
    public void list(){
        //如果头节点的下一位是null，那链表为空
        if(head.getNext() == null){
            System.out.println("链表为空");
            return;
        }
        //再准备一个临时变量，用于遍历
        Node temp = head;
        while (true){
            temp = temp.getNext();
            System.out.println(temp);
            if(temp.getNext() == null){
                break;
            }
        }
    }

4.进行数据的添加

在run类中创建链表对象并添加相应的数据进去添加数据

public class run {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(new Node(1,"cattle","girl"));
        singleLinkedList.add(new Node(2,"bob","boy"));
        singleLinkedList.add(new Node(3,"cat","girl"));

        singleLinkedList.list();
    }
}

编译结果

?5.根据ID大小进行添加

思路分析
1.Node节点中有一个id值，根据id值进行排序插入节点
2.如果链表中有id = 1,id = 3的两个节点，那插入一个id = 2的节点就要把它插入1,3中间
3.需要一个temp节点来找位置

public void addById(Node node){
        //情况1，链表为空，直接把数据放进去
        if(head.getNext() == null){
            add(node);
            return;
        }
        Node temp = head.getNext();
        //情况2，判断node有没有相同的id的
        while (true){
            if (node.getI() == temp.getI()){
                System.out.println("添加失败，该值已存在");
                return;
            }
            //已经遍历完并没有出现相同的值
            if(temp.getNext() == null){
                temp = head.getNext();
                break;
            }
            temp = temp.getNext();
        }
        //情况3.node.id的值比链表所有的值都小
        if(node.getI() < temp.getI()){
            node.setNext(temp);
            head.setNext(node);
            return;
        }
        while (true) {
            //情况4.当前只有一个值，或者temp已经到了右边界
            if(temp.getNext() == null){
                add(node);
                break;
            }
            //情况5，链表不为空，且存在多个不同的值
            if (temp.getI() < node.getI() && temp.getNext().getI() > node.getI()) {
                node.setNext(temp.getNext());
                temp.setNext(node);
                break;
            }
            temp = temp.getNext();
        }
    }

?根据ID大小添加数据的情况比较多，根据不同情况执行不同的指令

6.修改节点

思路分析：
1.根据遍历方法找到对应id值的节点
2.对节点进行修改

public void updateNode(Node node){
        if(head.getNext() == null){
            System.out.println("链表为空，无法修改");
            return;
        }
        Node temp = head.getNext();
        while (true){
            if(temp.getI() == node.getI()){
                temp.setName(node.getName());
                temp.setSex(node.getSex());
                return;
            }
            if(temp.getNext() == null){
                System.out.println("未找到该节点");
                return;
            }
            temp = temp.getNext();
        }
    }

7.删除节点

思路分析：
1.传入需要删除的节点的id
2.使用temp.getNext节点遍历找到对应节点位置，如不存在，打印节点不存在
3.删除，让temp.setNext为temp.getNext.getNext

public void deleteNode(int id){
        if(head.getNext() == null){
            System.out.println("链表为空");
            return;
        }
        Node temp = head;
        while (true){
            if(temp.getNext() == null){
                System.out.println("未找到该节点");
                return;
            }
            if(temp.getNext().getI() == id){
                temp.setNext(temp.getNext().getNext());
                break;
            }
            temp = temp.getNext();
        }
    }

二、单链表常见面试题

1.求单链表中的节点个数

思路分析：
1.创建一个计数器，每次找到节点让计数器加一
2.通过遍历的方式找到节点个数

public int getSize(){
        int count = 0;
        //如果链表为空，直接返回0
        if(head.getNext() == null){
            return count;
        }
        //遍历链表获取节点数
        Node temp = head;
        while (true){
            if (temp.getNext() == null){
                break;
            }
            count++;
            temp = temp.getNext();
        }
        return count;
    }

2.查找链表中的倒数第k个节点

思路分析：
1.获得最大尺寸getSize
2.倒数第k个节点即正数的(getSize - k + 1)个
3.需要看这个数是否合理

public void findRec(int k){
        if(k > getSize() || k == 0){
            System.out.println("输入的数字不合理");
            return;
        }
        Node temp = head;
        int x = (getSize() - k + 1);
        while (x > 0){
            temp = temp.getNext();
            x--;
        }
        System.out.println(temp);
    }

3.单链表的反转

插入法
思路分析：
1.创建一个新的头节点
2.顺序遍历原始链表，每一次遍历都取出当前值，并且插入到新节点的next，并让取出的节点的next指向头节点的next
注：
所有链表数据都是公共的，每一个next的修改都会影响到原始链表
最最重要的是要考虑到引用数据类型的传参是地址

public void rollback(){
        if(head.getNext() == null){
            System.out.println("链表为空");
            return;
        }
        Node node = new Node(0, "", "");
        Node temp = head.getNext();
        while (true){
            if(temp == null){
                break;
            }
            if(node.getNext() == null){
                //防止影响后续数据，第一次取出第一个节点后，让第一个节点的next为空
                //此时，为了不影响temp的取值，让temp提前指向next
                node.setNext(temp);
                temp = temp.getNext();
                node.getNext().setNext(null);
            }else {
                //此时链表中已经有两个节点，分别为头节点和第一个节点
                //取出temp当前指向的节点，并把该节点连入node中
                Node temptemp = node.getNext();
                node.setNext(temp);
                temp = temp.getNext();
                node.getNext().setNext(temptemp);
            }
        }
        head.setNext(node.getNext());
    }

4.合并两个有序单链表

思路分析：
1.因为是有序链表，所以可以直接遍历合并
2.创建两个指针temp01,temp02,用来遍历两个链表
3.判断链表是否为空或者是否取完
4.每次每个链表取出一个元素，对比两个值的大小，小的放前，大的放后，并且大的再次和另一个链表的第二个值对比

public static SingleLinkedList getTogether(SingleLinkedList linkedList01,SingleLinkedList linkedList02){
        if(linkedList01.head.getNext() == null || linkedList02.head.getNext() == null){
            throw new NullPointerException("链表为空");
        }
        SingleLinkedList list = new SingleLinkedList();
        Node node = new Node(0,"","");
        Node temp = node;
        Node temp01 = linkedList01.head.getNext();
        Node temp02 = linkedList02.head.getNext();
        while (true){
            //情况一：temp01>=temp02
            if(temp01.getI() >= temp02.getI()){
                temp.setNext(temp02);
                temp = temp.getNext();
                temp02 = temp02.getNext();
            }else if(temp01.getI() < temp02.getI()){//情况二：temp01<temp02
                temp.setNext(temp01);
                temp = temp.getNext();
                temp01 = temp01.getNext();
            }
            //情况三：如果此时到最后，temp01链表已经取空，temp02还有几个值没有取出来
            if(temp01 == null){
                temp.setNext(temp02);
                break;
            }else if(temp02 == null){
                temp.setNext(temp01);
                break;
            }
        }
        list.head.setNext(node.getNext());
        return list;
    }

三、双向链表

与单向链表的区别便是在节点中多了一个pre属性，让遍历时的指针可以向前向后选择

1.创建双向链表

（1）创建节点

public class Node {
    private int id;
    private String name;
    private String sex;
    private Node next;
    private Node pre;
}

（2）创建链表

public class DoubleLinkedList {
    private Node head = new Node(0,"","");
}

2.加入添加，遍历方法

总的来说，添加与遍历方法与单向链表无太大差异

（1）添加方法

思路分析：
1.与单向链表相似，不能修改头节点位置，需要一个temp节点
2.让temp节点获得head节点的位置，即指向
3.让temp的next指向加入的节点，让加入的节点的pre指向temp
4.判断temp节点的下一位是否为空，为空就添加，不为空下移

 public void add(Node node){
        Node temp = head;
        while (true) {
            if (temp.getNext() == null) {
                temp.setNext(node);
                node.setPre(temp);
                break;
            }
            temp = temp.getNext();
        }
    }

（2）遍历方法

public void list(){
        if(head.getNext() == null){
            System.out.println("双向链表为空");
            return;
        }
        Node temp = head;
        while (true){
            if(temp.getNext() == null){
                break;
            }
            temp = temp.getNext();
            System.out.println(temp);
        }
    }

3.删除方法

思路分析：
1.创建temp指针，遍历链表
2.根据所提供的id查找与之id相同的节点
3.让该节点的前一个节点的next指向该节点的next,让该节点的后一个节点的pre指向该节点的pre

   public void deleteNode(int id){
        if(head.getNext() == null){
            System.out.println("双向链表为空");
            return;
        }
        Node temp = head;
        while (true){
            if(temp.getNext() == null){
                System.out.println("未找到该节点");
                return;
            }
            temp = temp.getNext();
            if(temp.getId() == id){
                temp.getPre().setNext(temp.getNext());
                temp.getNext().setPre(temp.getPre());
                break;
            }
        }
    }

4.修改方法

思路分析：
1.传入一个修改好的node对象，根据node对象的id来找节点位置
2.再次采用temp节点来指

public void updateNode(Node node){
        if(head.getNext() == null){
            System.out.println("链表为空");
            return;
        }
        Node temp = head;
        while (true){
            if(temp.getNext() == null){
                System.out.println("未找到对应节点");
                break;
            }
            temp = temp.getNext();
            if(temp.getId() == node.getId()){
                temp.setName(node.getName());
                temp.setSex(node.getSex());
                break;
            }
        }
    }

5.按id添加，且无重复

思路分析：
1.判断加入进来的node的id大小
2.顺序遍历，直到出现比node的id大的节点
3.把node插入比他大的节点的前面
4.如果链表为空，直接加入
5.如果到达链表的末尾，直接加入

public void addById(Node node){
        if(head.getNext() == null){
            add(node);
            return;
        }
        Node temp = head;
        while (true){
            if(temp.getNext() == null){
                add(node);
                break;
            }
            temp = temp.getNext();
            if(node.getId() == temp.getId()){
                System.out.println("该节点已存在");
                return;
            }
            if(node.getId() < temp.getId()){
                temp.getPre().setNext(node);
                node.setPre(temp.getPre());
                node.setNext(temp);
                temp.setPre(node);
                break;
            }
        }
    }

四、环形链表

1.环形链表创建

（1）节点类，与单向链表一样

public class Node {
    //三个属性用于存储数据
    private int i;
    private String name;
    private String sex;
    //Node属性用于连接各个节点
    private Node next;
}

（2）链表

在未加入节点之前，指针为空

public class CircularLinkedList {
    //环形链表第一个节点的指针
    private Node first;
}

2.添加与遍历

（1）添加方法

思路分析：
1.使用temp节点去遍历，在temp.getNext == first时遍历完环形链表，在此处添加节点
2.让temp的next指向该节点，该节点的next指向first节点

public void add(Node node){
        //如果此时first指针为空，那么环形链表为空，就将添加进来的第一个节点作为first指针指向地
        if(first == null){
            first = node;
            node.setNext(node);
            return;
        }
        Node temp = first;
        //如果此时链表中只有一个节点，直接加入
        //这里主要是思路分析，其实在代码中可以忽略此步骤
        if(first.getNext() == first){
            temp.setNext(node);
            node.setNext(first);
            return;
        }
        //当前存在多个节点，加入数据需要遍历
        while (true){
            if(temp.getNext() == first){
                temp.setNext(node);
                node.setNext(first);
                break;
            }
            temp = temp.getNext();
        }
    }

（2）遍历方法

public void list(){
        if(first == null){
            System.out.println("环形链表为空");
            return;
        }
        Node temp = first;
        while (true){
            System.out.println(temp);
            temp = temp.getNext();
            if(temp == first){
                break;
            }
        }
    }

3.约瑟夫问题的删除方法

（1）约瑟夫问题

Josephu(约瑟夫、约瑟夫环)? 问题

Josephu? 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列

（2）删除方法

思路分析：
1.传入一个int值，用于决定转多少次，每次转到的节点都会被打印并删除
2.使用temp进行循环遍历，每次int计数结束删除当前指向的数
3.如果被删除的是first指针所在节点数，让first指针指向下一个
4.当first指针为空时，退出循环
5.要让temp删除某一节点，就要让temp从first前一位开始数

public void JosephDelete(int i){
        if(first == null){
            System.out.println("链表为空");
            return;
        }
        //让temp指向first
        Node temp = first;
        //将temp变为指向first前一个节点的位置
        while (true){
            if(temp.getNext() == first){
                break;
            }
            temp = temp.getNext();
        }
        int count = i;
        while (true){
            //此时链表里已经没有数据了
            if(first == null){
                break;
            }
            //让指针根据计数值指，直到计数结束
            while ((--count) > 0){
                temp = temp.getNext();
            }
            count = i;
            //如果当前指针指向了first指针所在节点，那么first指针下移
            if(temp.getNext() == first){
                //如果first指针的下一位为空，那么让first指针置空
                if(first.getNext() == first){
                    System.out.println("取出了 " + first);
                    first = null;
                }else {
                    System.out.println("取出了 " + temp.getNext());
                    temp.setNext(first.getNext());
                    first = first.getNext();
                }
            }else {
                //当指针指向其他节点时
                System.out.println("取出了 " + temp.getNext());
                temp.setNext(temp.getNext().getNext());
            }
        }
    }