3.链表

3.链表
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

目录

1.单链表
 1.1 单链表介绍
 1.2 单链表常见面试题
2.双向链表
3.单向环形链表

1.单链表

1.1 单链表介绍

链表是有序的列表,但是它在内存中是存储如下的:
在这里插入图片描述

1.链表是以节点的方式来存储,是链式存储
2.每个节点包含两个域:data 域、 next 域:指向下一个节点
3.链表的各个节点不一定是连续存储
4.链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定
 
单链表(带头结点) 逻辑结构示意图:在这里插入图片描述

直接尾部添加节点示意图,请注意辅助节点temp位置,下同:
在这里插入图片描述
按照升序添加节点示意图:
在这里插入图片描述
删除结点示意图(找到需要删除结点前一个节点temp):
在这里插入图片描述
被删除的节点,将不会有其它引用指向它,会被JVM的垃圾回收机制回收。

package linkedList;

import java.util.LinkedList;

class Node {
   
    public int data;
    public Node next;

    public Node() {
   
    }

    public Node(int data) {
   
        this.data = data;
    }
}

//定义单链表管理节点
public class SingleLinkedList {
   

    //先初始化一个头节点,作为单链表入口,不存放具体数据
    private Node head = new Node();

    /** * 返回链表的尾节点 * @return */
    public Node getLast(){
   
        //为了保持head节点不动,添加辅助节点temp遍历
        Node temp = head;
        //遍历链表,找到尾节点
        while (temp.next!=null){
   
            temp = temp.next;
        }
        return temp;
    }

    /** * 添加节点到单向链表尾部 * 当不考虑数据排序时:1.找到当前链表的尾节点 2.将最后这个节点的next指向新的节点 */
    public void add(Node node){
   
        Node temp = getLast();
        node.next = null;
        temp.next = node;
    }

    /** * 按照升序将节点插入到指定的位置 * 因为头节点不能动,因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置 * 因为单链表,因为我们找的 temp 是位于 添加位置的前一个节点,否则插入不了 */
    public void addByOrder(Node node){
   
        Node temp = head;
        while (true){
   //从链表中第一个节点开始陆续比较(temp.next),如果新节点的值小于比较节点,则插入比较节点前。
            //已经插入了链表的节点不能再插入,
            if (temp.next==node){
   
                System.out.println("节点:"+node+"已经存在!");
                break;
            }
            //第一种情况:要比较的节点没有了,说明新增节点最大。
            //第二种情况:新节点值比与之比较的节点值小,则插入该节点前,当前节点(temp)后。
            else if (temp.next == null || temp.next.data >= node.data){
   
                node.next = temp.next;
                temp.next = node;
                break;
            }
            temp = temp.next;
        }
    }

    /** * 显示单链表所有数据 */
    public void show(){
   
        if (head==null){
   
            System.out.println("链表为空");
            return;
        }
        Node temp = head.next;
        while (temp!=null){
   
            System.out.println(temp.data);
            temp = temp.next;//temp后移
        }
    }

    /** * 删除结点 * 1. head 不能动,因此我们需要一个 temp 辅助节点找到待删除节点的前一个节点 * 2. 说明我们在比较时,是 temp.next 和 需要删除的节点的 node 比较 */
    public void remove(Node node){
   
        Node temp = head;
        while (null != temp.next){
   
            if (temp.next == node){
   //找到要删除的节点
                temp.next = node.next;
                break;
            }
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
   
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(2);
        Node node5 = new Node(4);
        SingleLinkedList list = new SingleLinkedList();
        list.addByOrder(node3);
        list.addByOrder(node1);
        list.addByOrder(node5);
        list.addByOrder(node4);
        list.addByOrder(node2);
        //list.addByOrder(node2);
        list.show();
        System.out.println("删除后");
        list.remove(node2);
        list.show();
    }

}

1.2 单链表常见面试题:

1.2.1 求单链表中有效节点的个数:直接遍历计数。

public static int getLength(Node head) {
   
        if (head.next == null) {
    //空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助的变量, 这里我们没有统计头节点
        Node temp = head.next;
        while(temp != null) {
   
            length++;
            temp = temp.next; //遍历
        }
        return length;
    }

2.查找单链表中的倒数第 k 个结点 【新浪面试题】:

	/** * //思路 * //1. 编写一个方法,接收 head 节点,同时接收一个 index * //2. index 表示是倒数第 index 个节点 * //3. 先把链表从头到尾遍历,得到链表的总的长度 getLength * //4. 得到 size 后,我们从链表的第一个开始遍历 (size-index)个,就可以得到 * //5. 如果找到了,则返回该节点,否则返回 null * @param head * @param index * @return */
    public Node findLastIndexNode(Node head, int index){
   
        //判断如果链表为空,返回 null
        if(head.next == null) {
   
            return null;//没有找到
        }
        //第一个遍历得到链表的长度(节点个数)
        int size = getLength(head);
        //第二次遍历 size-index 位置,就是我们倒数的第 K 个节点
        //先做一个 index 的校验
        if(index <=0 || index > size) {
   
            return null;
        }
        //定义给辅助变量, for 循环定位到倒数的 index
        Node temp = head.next; //3 // 3 - 1 = 2
        for(int i =0; i< size - index; i++) {
   
            temp = temp.next;
        }
        return temp;
    }

3.单链表的反转【腾讯面试题】,提供两种思路:

第一种方案,直接在原单链表上操作:

	/** * 思路1:单链表反转也就是next指向反过来 * 1.两个辅助变量cur和next分别用于访问单链表的两个连续节点,将第二个节点的next改为指向第一个节点。 * 2.由于第二个节点的next指向了第一个节点,便无法继续访问到第二个节点后面的节点了, * 所以需要在改变第二个节点next指向前,提前用第三个辅助变量temp将第二个节点的后一个节点备份下来。以此循环。 * 3.循环到达当第二个节点为空时,说明没有需要改变指向的节点了,退出循环,将原先的head头指针指向此时第一个 * 节点(原链表的最后一个节点)即可。 * @param head */
    public void reverseList1(Node head){
   
        if (head.next==null || head.next.next==null){
   //当前节点为空,或只有一个节点无需反转,直接返回
            return;
        }
        Node cur = head.next;
        Node next = cur.next;
        while (next!=null){
   
            Node temp = next.next;
            next.next = cur;//改变next指向
            if (cur==head.next){
   //反转指向后,若为第一个节点反转后将作为最后一个节点,next指向应为null
                cur.next = null;
            }
            //节点后移
            cur = next;
            next = temp;
        }
        head.next = cur;
    }

第二种方案,利用一个辅助单链表操作:

	/** * 思路2: * 1.定义一个临时辅助头节点reverseHead * 2.从头到尾遍历原链表节点,每访问到一个节点,将其取出,取出则相当于断开与原链表连接,放到临时头节点reverseHead最前端 * 3.将原头节点指向临时头节点下一节点:head.next = reverseHead.next; * @param head */
    public void reverseList2(Node head){
   
        if (head.next==null || head.next.next==null){
   //当前节点为空,或只有一个节点无需反转,直接返回
            return;
        }
        //定义辅助变量用于访问原链表结点
        Node cur = head.next;
        //定义临时头节点
        Node reverseHead = new Node();
        //遍历原链表节点,每访问到一个节点,将其取出,放到临时头节点最前端
        while (cur != null){
   
            Node temp = cur.next;//在取出cur前提前访问备份cur的下一节点,避免取出后丢失指向。
            //关键一步,将cur放到临时头节点指向的新链表的最前端。
            cur.next = reverseHead.next;
            reverseHead.next  = cur;
            //继续访问原链表
            cur = temp;
        }
        head.next = reverseHead.next;
    }

4.从尾到头打印单链表 【百度】,该题依旧提供两种思路:

第一种方案:容易想到,先利用上述的方法将单链表反转,然后再顺序打印即可。但是该方案不建议:这样会破坏原单链表的结构,要求只是逆序打印,但该方法却把链表节点都反转了。 如果又再次要求需要正序打印,或者这个链表很大,这就得不偿失了。

第二种方案:利用栈的数据结构,先进后出,实现逆序打印。

	public void reversePrint(Node head){
   
        if (head.next==null){
   
            return;
        }
        Node cur = head.next;
        Stack<Node> stack = new Stack<>();
        while (cur!=null){
   
            stack.push(cur);
            cur = cur.next;
        }
        //出栈打印
        while (!stack.isEmpty()){
   
            System.out.println(stack.pop().data);
        }
    }

5.合并两个有序的单链表,使合并之后的链表依然有序:

	/** * 新建一个单链表,每次都把两个有序链表中的更小的值加入到新链表中 * @param head1 * @param head2 * @return */
    public Node mergeOrderedList(Node head1, Node head2){
   
        Node newHead = new Node();
        Node tempHead = newHead;
        Node cur1 = head1.next;
        Node cur2 = head2.next;
        while (cur1 != null && cur2 != null) {
   
            if (cur1.data <= cur2.data) {
   
                tempHead.next = new Node(cur1.data);
                tempHead = tempHead.next;
                cur1 = cur1.next;
            } else {
   
                tempHead.next = new Node(cur2.data);
                tempHead = tempHead.next;
                cur2 = cur2.next;
            }
        }
        if (cur1 == null) {
   //链表2更长
            while (cur2 != null) {
   
                tempHead.next = new Node(cur2.data);
                tempHead = tempHead.next;
                cur2 = cur2.next;
            }
        } else {
   //链表1更长
            while (cur1 != null) {
   
                tempHead.next = new Node(cur1.data);
                tempHead = tempHead.next;
                cur1 = cur1.next;
            }
        }
        return newHead;
    }

2.双向链表

双向链表相较于单向链表的优点:

1.单向链表查找的方向只能是一个方向,而双向链表可以向前或者向后查找;
2.单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除。

数据结构(java):

class Node {
   
    public int data;
    public Node next;
    public Node pre;
    
    public Node() {
   
    }

    public Node(int data) {
   
        this.data = data;
    }
}

在这里插入图片描述
分析双向链表易发现:

1.遍历方法和单链表一样,只是可以向前,也可以向后查找;
2.添加新节点到双向链表的尾部的方法也和单链表差不多,只是多一个pre向前指向;
3.修改思路也和单向链表一样。
4.而对于删除,因为是双向链表,因此可以实现自我删除某个节点:直接找到要删除的这个节点,比如temp,temp.pre.next = temp.next,temp.next.pre = temp.pre;

3.单向环形链表

在这里插入图片描述
首先来看单向环形链表的一个应用场景,经典的Josephu(约瑟夫)问题:

设编号为 1,2,… n 的 n 个人围坐一圈,约定编号k(1<=k<=n)的人(即圈中随机一个人开始)从 1 开始报数,数到 m 的那个人出列,它的下一位又从 1 开始报数,数到 m 的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。

通过单向环形链表解决约瑟夫问题的分析(当然,也可以用数组取模的方式模拟环):

用一个不带头节点的循环链表来处理 Josephu 问题:先构成一个有 n 个节点的单循环链表,然后由 k 节点起从 1 开始计数,计到 m 时,对应节点从链表中删除,然后再从被删除节点的下一个节点又从 1 开始计数,直到最后一个节点从链表中删除算法结束(一个节点也能形成环)。将这个删除节点的过程记录,则得出了约瑟夫问题中想要的编号序列。

基于前面的概念,再来看单向环形链表的构建思路:

1.与单向链表head头节点不同的是,单向环形链表没有头节点,但是它需要记录环的一个入口节点first(也是出口节点),指向加入链表的第一个节点的地址。
2.这样每次操作单向循环链表时,则从入口节点first开始,其作用类似于头节点。

完整解决约瑟夫问题代码如下:

package linkedList;

class Boy{
   
    public int no;//小孩编号,相当于身份证
    public Boy next;

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

class CircleSingleLinkedList{
   
    private Boy first = null;//入口节点第一个节点

    /** * 根据输入的k值,生成小孩出圈序列: * 1.同单向链表删除节点,需要辅助节点指向待删除结点的前一个节点,辅助节点和数数的当前节点同步移动。 * 2.例:n=5,k=1,m=2,从no为1的小孩开始报数,数两下(节点移动1位,辅助节点移动m-1位,即不动)。 * 3.小孩报数前,首先找到开始开始报数的节点,first节点和辅助节点移动k-1次 * 4.小孩报数时,first节点和辅助节点同时移动m-1次,first此时指向节点即为要删除结点。 * @param startNo k值 * @param countNum m值 * @param nums n值 */
    public void getOutOrder(int startNo, int countNum, int nums){
   
        if (first==null || startNo<=0 || startNo > nums){
   
            return;
        }
        Boy temp = first;
        //首先将辅助节点指向入口节点的后一位,数数时同步移动
        while (temp.next!=first){
   
            temp = temp.next;
        }
        //重置入口节点到指定的k节点处
        for (int i = 0; i < startNo - 1; i++) {
   
            first = first.next;
            temp = temp.next;
        }
        //开始报数出圈
        while (first.next != first){
   
            //先报数,即移动访问节点
            for (int i = 0; i < countNum - 1; i++) {
   
                first = first.next;
                temp = temp.next;
            }
            System.out.printf("小孩%d出圈~\n",first.no);
            //再出圈,即删除节点
            first = first.next;
            temp.next = first;

        }
        //最后一个小孩出圈
        System.out.printf("小孩%d出圈~",first.no);
    }

    /** * 添加小孩节点,形成单向环形链表。 * 为了方便,从1开始,nums即为要添加小孩数量,批量添加小孩节点 * @param nums */
    public void addBoys(int nums){
   
        if (nums<=0){
   
            return;
        }
        Boy curBoy = null;//辅助节点,用于访问链表
        for (int i = 1; i <= nums; i++) {
   
            Boy boy = new Boy(i);
            if (i==1){
   //指定第一个小孩为入口节点,特殊处理
                first = boy;
                boy.next = first;
                curBoy = boy;
            }else {
   
                curBoy.next = boy;
                boy.next = first;
                curBoy = boy;
            }
        }
    }

    /** * 遍历单向环形链表,显示所有小孩 */
    public void showBoys(){
   
        if (first==null){
   
            System.out.println("没有小孩");
            return;
        }
        Boy curBoy = first;
        while (true){
   
            System.out.println(curBoy.no);
            curBoy = curBoy.next;
            if (curBoy==first){
   
                break;
            }
        }
    }

}

public class Josephu {
   

    public static void main(String[] args) {
   
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoys(5);
        System.out.println("围成圈的小孩:");
        circleSingleLinkedList.showBoys();
        System.out.println("开始出圈:");
        circleSingleLinkedList.getOutOrder(1,2,5);
    }
}
本文来源MrKorbin,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/25283

发表评论