登录
当前位置： 首页 > 知识库问答 >
问题：

升序循环链表

佟嘉祯
2023-03-14

我的任务是用java实现一个循环链表（升序），但问题是它在无限循环中运行

我创建了一个节点类，其中定义了两个元素。

public class Node {
    public int element;
    public Node next;

    public class Node {
        int element;
        Node next;
    }
}

现在，在列表的第二个类中，我做了一个insert函数，我在start中定义了一个节点head=null，并创建了一个新的nNode。之后，我在head部分中检查，如果head==null，那么第一个元素将是nNode。插入第一个元素后，我将比较下一个元素和head元素，如果head元素大于，它将移动下一个，新的nNode将是head。因为它是循环链表，所以它是工作的，但是它也在无限循环中运行。

这是List类，我在其中使用了node类变量

public class List {
    void insert(int e) {
        Node nNode = new Node();
        Node tNode = head;
        nNode.element = e;

        if (head == null)
            head = nNode;                      
        else if (head.element > e) {                        
            nNode.next = head;
            head=nNode;
        } else {
            Node pNode = head;

            while (tNode.next != head && tNode.element <= e) {
                pNode = tNode;
                tNode = tNode.next;
            }

            pNode.next = nNode;
            nNode.next = tNode;
            tNode.next=head;                                           
        }
    }
}

共有1个答案

空慈
2023-03-14

我已经创建了循环链接列表的示例程序，其中包含给定元素的名称和年龄。它有add()、remove()和sorbasedonage()（排序是通过先获取克隆并将其转换为简单的链表来实现的，然后使用合并排序，这样可以达到O（nLogn）的性能。）

如果你喜欢，别忘了按like按钮。

package com.ash.practice.tricky;

import java.util.Collections;
import java.util.LinkedList;

public class CircularLinkedList implements Cloneable{

Node start;

public Node getHead() {
    return start;
}

CircularLinkedList setHead(Node startNode) {
    start = startNode;
    return this;
}

public void add(String name, int age) {

    if(name==null) {
        System.out.println("name must not be null.");
        return;
    }

    if(start == null) {
        Node node = new Node(name,age);
        start = node;
        node.next = start;
    } else {

        Node node = new Node(name,age);
        Node temp = start;
        while(temp.next != start) {
            temp = temp.next;
        }
        temp.next = node;
        node.next = start;
    }
}

public CircularLinkedList clone()throws CloneNotSupportedException{  
    return (CircularLinkedList)super.clone();  
}  

public boolean remove(String name) {
    if(name==null) {
        return false;
    } else if(start==null) {
        return false;
    } else if(start.getName().equals(name)) {
        if(size()>1) {
            Node temp = start;
            while(temp.next!=start) {
                temp = temp.next;
            }
            temp.next = start.next;
            start = start.next;
        } else {
            start = null;
        }
        return true;
    } else {
        Node temp = start;
        Node next = null;
        Node prev = null;

        while(temp.next != start) {
            String currName = temp.name;
            if(currName.equals(name)) {
                next = temp.next;
                break;
            } else {
                temp = temp.next;
            }
        }
        if(next == null) {
            return false;
        }
        prev = temp.next;
        while(prev.next!=temp) {
            prev = prev.next;
        }
        prev.next = next;
        temp = null;
        return true;
    }
}

/*  

public Node getPrevious(String name, int age) {
    Node curr = new Node(name,age);
    Node temp = curr;
    while(temp.next!=curr) {
        temp = temp.next;
    }
    return temp;
}

 */

public int size() {
    int count = 1;
    if(start != null) {
        Node temp = start;
        while(temp.next!=start) {
            count++;
            temp = temp.next;
        }
    } else return 0;
    return count;
}

public int listSize() {
    int count = 1;
    if(start != null) {
        Node temp = start;
        while(temp.next!=null) {
            count++;
            temp = temp.next;
        }
    } else return 0;
    return count;
}

public void display() {
    if(start == null) {
        System.out.println("No element present in list.");
    } else {
        Node temp = start;
        while(temp.next != start) {
            System.out.println(temp);
            temp = temp.next;
        }
        System.out.println(temp);
    }
}

public void displayList() {
    if(start == null) {
        System.out.println("No element present in list.");
    } else {
        Node temp = start;
        while(temp.next != null) {
            System.out.println(temp);
            temp = temp.next;
        }
        System.out.println(temp);
    }
}

public Node getPrevious(Node curr) {
    if(curr==null) {
        return null;
    } else {
        Node temp = curr;
        while(temp.next!=curr) {
            temp = temp.next;
        }
        return temp;
    }
}

Node getMiddle() {
    Node result = null;
    Node temp = start.next;
    result = start.next;
    Node end = getPrevious(start);
    end.next = null;

    while(temp.next!=null) {
        if(temp.next.next!=null) {
            temp = temp.next.next;
            result = result.next;
        } else {
            return result;
        }
    }
    return result;
}

private static CircularLinkedList SortCollections(CircularLinkedList list) {
    return SortCollections.doSortBasedOnAge(list);
}

private static class Node {
    Node next;
    String name;
    int age;

    Node(String name,int age) {
        this.name = name;
        this.age = age;
    }

    String getName() {
        return name;
    }

    int getAge() {
        return age;
    }

    public String toString() {
        return "name = "+name +" : age = "+age;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Node other = (Node) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }
}

private static class SortCollections {

    static Node mergeSort(Node head) {
        if(head == null || head.next == null) {
            return head;
        }

        Node middle = getMiddle(head);
        Node nextHead = middle.next;
        middle.next = null;

        Node left = mergeSort(head);
        Node right =  mergeSort(nextHead);
        Node sortedList = sortedMerged(left, right);
        return sortedList;
    }

    public static  CircularLinkedList doSortBasedOnAge(CircularLinkedList list) {
        CircularLinkedList copy = null;
        try {
            copy = list.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }

        if(copy!=null) {
            Node head = copy.getHead();
                            Node end = copy.getPrevious(head);
            end.next = null;
            Node startNode = mergeSort(head);

            CircularLinkedList resultList = new CircularLinkedList().setHead(startNode);
            return resultList;
        } else {
            System.out.println("copy is null");
        }
        return null;
    }

    private static Node sortedMerged(Node a, Node b) {
        if(a == null) {
            return b;
        } else if(b == null) {
            return a;
        }

        Node result = null;
        if(a.getAge() > b.getAge()) {
            result = b;
            result.next = sortedMerged(a, b.next);
        } else {
            result = a;
            result.next = sortedMerged(a.next, b);
        }

        return result;
    }

    private static Node getMiddle(Node head) {
        Node result = null;
        Node temp = head;
        result = head;

        while(temp.next!=null) {
            if(temp.next.next!=null) {
                temp = temp.next.next;
                result = result.next;
            } else {
                return result;
            }
        }
        return result;
    }

}
public static void main(String[] args) {

    CircularLinkedList list = new CircularLinkedList();
    Collections.sort(new LinkedList());
    list.add("ashish", 90);
    list.add("rahul", 80);
    list.add("deepak", 57);
    list.add("ankit", 24);
    list.add("raju", 45);
    list.add("piyush", 78);
    list.add("amit", 12);
    //list.display();
    /*System.out.println("---------------- size = "+list.size());
    System.out.println(list.remove("deepak"));
    //list.display();
    System.out.println("---------------- size = "+list.size());
    System.out.println(list.remove("ashish"));
    //list.display();
    System.out.println("---------------- size = "+list.size());
    System.out.println(list.remove("raju"));
    //list.display();
    System.out.println("---------------- size = "+list.size());
    list.add("aman", 23);
    System.out.println("---------------- size = "+list.size());
    list.display();
    System.out.println("Previous Node of second node is : "+list.getPrevious(list.start.next));
    System.out.println("Previous Node of start node is : "+list.getPrevious(list.start));
    System.out.println("Previous Node of piyush node is : "+list.getPrevious("piyush",78));*/
    list.display();
    System.out.println("---------------- size = "+list.size());
    //System.out.println(list.getMiddle());
    CircularLinkedList newList = CircularLinkedList.SortCollections(list);
    newList.displayList();
    System.out.println("---------------- size = "+newList.listSize());
}

}

 类似资料：
  • 循环链表无限循环

    我正在用我的java书复习数据结构，我需要重新创建一个循环链表。我对这个无限循环的链表有问题，弄不清楚为什么。我可以将值插入到列表中，但是打印和删除这些值似乎会无限循环最初插入的值。我如何更改我的List类以避免无限循环？ CircularList.Class 链接类

  • 循环双链表无限循环

    基本上，findNode()搜索其数据等于作为参数插入的字符串的节点，但当我调用outputList（）方法（该方法返回屏幕上当前节点的字符串表示）时，它将继续无限循环。 outputList方法是： 如有任何帮助，我们将不胜感激。提前道谢。

  • 合并排序循环链表C

    我试图用C语言合并排序列表。我在法语维基百科上看到了这里的代码，但它给了我一个不正确的列表（即未排序）。不过，该函数编译得很好。请注意，我并没有真正使用top，我可能很快就会把它从结构中去掉。你能帮我找出这个代码的错误吗？我必须把它从算法伪代码翻译成C代码。非常感谢。 是未排序的输入列表。是列表的长度。

  • 双循环链表

    我创建了一个双循环链表。 我需要知道每个节点到头部的距离。 因为当我必须删除或获取具有特定密钥的节点时，如果两个节点具有相同的密钥和相同的距离，则必须删除或获取这两个节点，否则必须删除最靠近头部的节点。 我不知道如何计算距离，因为它是圆形的。。。 这个链表的插入就是这样工作的。 所有的节点都去追头。 例： 1）头部 2） 头部A（插入A） 3） 头部B-A（插入B） 4） 头部C-B-A（插入C）

  • 双向循环链表

    双向循环链表 在“数据结构”课程中，如果创建某种数据结构的双循环链表，通常采用的办法是在这个数据结构的类型定义中有专门的成员变量 data, 并且加入两个指向该类型的指针next和prev。例如： typedef struct foo { ElemType data; struct foo *prev; struct foo *next; } foo_t; 双向循环链表的

  • Selenium循环链接

    在selenium中，在python中，我必须循环使用Jira1、jira2、jira3链接 对于范围（1,4）中的i： driver.find_element（By.XPATH，"//a[text（）='Jira'] /str（i）"）。 它给了我一个错误NoSuchElementException:没有这样的元素：无法定位元素：{“方法”：“xpath”，“选择器”：“//a[text（）='

相关问答

Selenium循环链接合并两个排序的循环单链表按升序和降序排序链表如何克隆循环链表在单链表中查找循环

相关文章

使用Selenium Webdriver（Python）循环链接common-lisp 循环序列循环似乎不遵循顺序访谈：删除链表中的循环-JavaJava如何检测链表中的循环？

相关阅读

Scala 循环Perl 循环Ruby 循环TypeScript 循环Lua 循环

相关工具

循环ScrollView循环洞穴2循环洞穴 2循环滚动视图升级树

相关文档

Windows 环境下 32 位汇编语言程序设计区块链教程MOAC 链中文文档Node.js 区块链开发区块链技术指南
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.