java实现链表

头插法建立单链表完整代码java #include#include#includetypedef struct Link {int elem;struct Link *next;}link;//无头结点链表的头插法实现函数link * creatLink(int * arc, int length) {int i;//最初状态下，头指针 H 没有任何结点，所以，插入第一个元素，就相当于是创建结点 Hlink * H =(link*)malloc(sizeof(link));H->elem = arc[0];H->next = NULL;//如果采用头插法插入超过 1 个元素，则可添加到第一个结点 H 之前for (i = 1; ilink * a = (link*)malloc(sizeof(link));a->elem = arc[i];//插入元素时，首先将插入位置后的链表链接到新结点上a->next = H;//然后再链接头指针 HH = a;}return H;}//有头结点链表的头插法实现函数link * HcreatLink(int * arc, int length) {int i;//创建头结点 H，其链表的头指针也是 Hlink * H = (link*)malloc(sizeof(link));H->elem = 0;H->next = NULL;//采用头插法创建链表for (i = 0; ilink * a = (link*)malloc(sizeof(link));a->elem = arc[i];//首先将插入位置之后的链表链接到新结点 a 上a->next = H->next;//将新结点 a 插入到头结点之后的位置H->next = a;}return H;}//链表的输出函数void display(link *p) {while (p) {printf("%d ", p->elem);p = p->next;}printf("\n");}int main() {int a[3] = { 1,2,3 };//采用头插法创建无头结点链表link * H = creatLink(a, 3); display(H);//采用头插法创建有头结点链表link * head = HcreatLink(a, 3); display(head);//使用完毕后，释放即可free(H);free(head); return 0; }。

listnode用法java -回复ListNode是一种常见的数据结构，经常用于解决与链表相关的问题。

在Java中，可以使用ListNode来表示一个链表，它由一个节点节点组成，每个节点都包含一个数据元素和一个指向下一个节点的指针。

在本文中，我们将探讨ListNode的使用方法，并逐步回答与之相关的问题。

I. ListNode的定义和基本操作1. 定义ListNode类首先，我们需要定义一个ListNode类，它包括一个数据元素和一个指向下一个节点的指针。

代码如下所示：javaclass ListNode {int val;ListNode next;ListNode(int val) {this.val = val;}}2. 创建链表要创建一个链表，我们需要实例化多个ListNode对象，并使用它们的next 指针连接起来。

下面是一个简单的示例：javaListNode head = new ListNode(1); 创建第一个节点head.next = new ListNode(2); 创建第二个节点head.next.next = new ListNode(3); 创建第三个节点这样，我们就创建了一个包含3个节点的链表，节点的值分别为1、2和3。

最后一个节点的next指针为空，表示链表的末尾。

3. 遍历链表要遍历链表，我们可以使用一个指针从头部开始，依次访问每个节点，并沿着next指针移动到下一个节点。

以下是一个遍历链表并输出节点值的示例：javaListNode curr = head;while (curr != null) {System.out.println(curr.val);curr = curr.next;}II. 解决与ListNode相关的问题接下来，我们将使用ListNode来解决几个常见的问题，包括链表的反转、检测环路和合并两个有序链表。

1. 反转链表反转链表是指将链表中的节点顺序颠倒。

Java用单链表实现多项式加减乘用单链表来实现多项式的加减乘，除就不做了，代码如下publicclassPolynomial{privateMonomialfirst;//首项//添加单项式publicvoidappend(Monomialmonomial){if(monomial==null){//donothing}elseif(first==null){first=monomial;}else{Monomialcurrent=first;while(current!=null){//Examda提示:如果指数相同，则相加if(current.index==monomial.index){current.coefficient+=monomial.coefficient;break;}elseif(current.next==null){//否则直接扔到最后current.next=monomial;break;}current=current.next;}}}publicvoidappend(doublec,inti){append(newMonomial(c,i));}publicStringtoString(){StringBuffersb=newStringBuffer();Monomialcurrent=first;while(current.next!=null){sb.append("("+current.coefficient+"x^"+current.index+")+");current=current.next;}sb.append("("+current.coefficient+"x^"+current.index+")");returnsb.toString();}//两个多项式相加publicPolynomialadd(Polynomialp2){Polynomialresult=newPolynomial();Monomialcurrent=this.first;while(current!=null){result.append(current.coefficient,current.index);//Examda提示:注意这里current=current.next;}current=p2.first;while(current!=null){result.append(current.coefficient,current.index);current=current.next;}returnresult;}//两个多项式相减this-p2publicPolynomialsubstract(Polynomialp2){Polynomialresult=newPolynomial();Monomialcurrent=this.first;while(current!=null){result.append(current.coefficient,current.index);//注意这里current=current.next;}current=p2.first;while(current!=null){result.append(-current.coefficient,current.index);current=current.next;}returnresult;}/***this*p2**@return*/publicPolynomialmultiply(Polynomialp2){ Polynomialresult=newPolynomial();Monomialc1=this.first;Monomialc2=p2.first;while(c1!=null){while(c2!=null){result.append(c1.coefficient*c2.coefficient,c1.index +c2.index);c2=c2.next;}c1=c1.next;c2=p2.first;}returnresult;}publicPolynomialdivide(Polynomialp2){//todo实现相除returnnull;}publicstaticvoidmain(String[]args){Polynomialp1=newPolynomial();p1.append(2.2,1);p1.append(3.3,2);p1.append(4.111,7);System.out.println("p1:"+p1);Polynomialp2=newPolynomial();p2.append(2.232,5);p2.append(3.444,6);p2.append(5.777,1);System.out.println("p2:"+p2); Polynomialresult=p1.add(p2); System.out.println("加:"+result); result=p1.substract(p2); System.out.println("减:"+result); result=p1.multiply(p2);System.out.println("乘:"+result); }}/***单项式*/classMonomial{doublecoefficient;//系数intindex;//指数Monomialnext;//后继结点publicMonomial(){}publicMonomial(doublec,inti){ this.coefficient=c;this.index=i;}}。

java遍历方式Java中遍历的方式有很多种，这里列举一些常见的遍历方法：1. 遍历数组：```javafor (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}```2. 遍历链表：```javafor (Node<String> node : list) {System.out.println(node.data);}```3. 遍历树：public void traverseTree(TreeNode<String> node) {if (node == null) {return;}System.out.println(node.data);traverseTree(node.left);traverseTree(node.right);}```4. 遍历HashMap：```javafor (Map.Entry<String, String> entry : map.entrySet()) {System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());}```5. 遍历Set：for (String item : set) {System.out.println(item);}```6. 遍历文件系统：```javaimport java.io.File;for (File file : directory.listFiles()) {if (file.isDirectory()) {System.out.println("Directory: " + file.getName());traverseDirectory(file);} else {System.out.println("File: " + file.getName());}}```这些只是Java中遍历方式的一部分，根据实际需求和数据结构，还有其他更多的遍历方法可供选择。

Java LinkedList 类提供了许多方法，用于操作链表。

以下是一些常用的LinkedList 方法：1. add(E e)：在链表末尾添加元素e。

2. add(int index, E element)：在指定位置index 插入元素element。

3. addFirst(E e)：在链表头部添加元素e。

4. addLast(E e)：在链表尾部添加元素e。

5. clear()：移除链表中的所有元素。

6. contains(Object o)：判断链表中是否包含元素o。

7. containsAll(Collection<?> c)：判断链表中是否包含集合c 中的所有元素。

8. get(int index)：获取链表中指定位置index 的元素。

9. getFirst()：获取链表头部的元素。

10. getLast()：获取链表尾部的元素。

11. remove(Object o)：移除链表中第一个出现的指定元素o。

12. remove(int index)：移除链表中指定位置index 的元素。

13. removeFirst()：移除链表头部的元素。

14. removeLast()：移除链表尾部的元素。

15. size()：返回链表中元素的个数。

16. isEmpty()：判断链表是否为空。

17. isSingleton()：判断链表是否只有一个元素。

18. poll()：移除并返回链表头部的元素，如果链表为空则返回null。

19. pop()：移除并返回链表尾部的元素，如果链表为空则抛出NoSuchElementException 异常。

20. peek()：返回链表头部的元素，但不移除，如果链表为空则返回null。

21. push(E e)：将元素e 添加到链表头部。

22. offer(E e)：将元素e 添加到链表尾部，如果成功则返回true，否则返回false。

23. removeFirstOccurrence(Object o)：移除链表中第一个出现的指定元素o。

双向链表逆序双向链表的逆序操作可以通过修改节点之间的引用关系来实现。

具体步骤如下：1. 定义三个指针：pre表示当前节点的前一个节点，cur表示当前节点，next表示当前节点的后一个节点；2. 遍历整个链表，初始时将pre设置为null，cur设置为链表的头节点；3. 在遍历过程中，先将next指向cur的后一个节点；4. 将cur的next指向pre，将cur的prev指向next。

5. 更新pre和cur，将cur指向next，pre指向cur；6. 重复步骤3~5，直到遍历到链表的最后一个节点。

7. 将最后一个节点的prev指向null，表示链表逆序完成。

以下是Java代码示例：```public class DoublyLinkedList {Node head;class Node {int data;Node prev;Node next;Node(int d) {data = d;prev = null;next = null;}}public void reverse() {Node temp = null;Node current = head;while (current != null) {temp = current.prev;current.prev = current.next;current.next = temp;current = current.prev;}if (temp != null) {head = temp.prev;}}}```注意：逆序之后，原来的头结点会变成尾结点，原来的尾结点会变成头结点。

单链表的操作方法一：package ch02;(1)建立结点类Node.javapublic class Node {public Object data;//存放结点数据值public Node next;//存放后继结点//无参构造函数public Node(){ this(null,null);}//只有结点值的构造函数public Node(Object data){ this(data,null);}//带有节点值和后继结点的构造函数public Node(Object data,Node next){ this.data=data;this.next=next;}}(2)建立链表及操作LinkList.javapackage ch02;import java.util.Scanner;public class LinkList implements IList{public Node head;//单链表的头指针//构造函数初始化头结点public LinkList(){head=new Node();}//构造函数构造长度为n的单链表public LinkList(int n,boolean Order) throws Exception{ this();if(Order)create1(n); //头插法顺序建立单链表elsecreate2(n); //尾插法逆序建立单链表}//头插法顺序建立单链表public void create1(int n) throws Exception{Scanner sc=new Scanner(System.in);System.out.println("请输入结点的数据(头插法)：”)；for(int i=0;i<n;i++){insert(0,sc.next());}}//尾插法逆序建立单链表public void create2(int n) throws Exception{Scanner sc=new Scanner(System.in);System. out.println("请输入结点的数据(尾插法)：");for(int i=0;i<n;i++){insert(length(),sc.next());}}//将链表置空public void clear(){head.data=null;head.next=null;}//判断链表是否为空public boolean isEmpty(){return head.next==null;}//返回链表长度public int length(){Node p=head.next;int length=0;while(p!=null){p=p.next;length++;//返回P不空长度length加1}return length;}//读取并返回第i个位置的数据元素public Object get(int i) throws Exception {Node p=head.next;int j;//从首结点开始向后查找，直到9指向第i个结点或者p为nullfor(j=0;j<i&&p!=null;j++){ p=p.next;}if(j>i||p==null)//i不合法时抛出异常throw new Exception("第"+i+”个数据元素不存在”)；return p.data;}//插入乂作为第i个元素public void insert(int i, Object x) throws Exception{ Node p=head;int j=-1;//寻找第i个结点的前驱i-1while(p!=null&&j<i-1){p=p.next;j++;}if(j>i-l||p==null)//i不合法时抛出异常throw new Exception("插入位置不合法”)；Node s=new Node(x);s.next=p.next;p.next=s;}//删除第i个元素public void remove(int i) throws Exception{ Node p=head;int j=-1;while(p!=null&&j<i-1){//寻找第i-1 个节点p=p.next;j++;}if(j>i-1||p.next==null)throw new Exception("删除位置不合法”)；p.next=p.next.next;}//返回元素x首次出现的位序号public int indexOf(Object x) {Node p=head.next;int j=0;while(p!=null&&!p.data.equals(x)){p=p.next;j++;if(p!=null)return j;elsereturn -1;}public void display(){Node p=head.next;while(p!=null){if(p.next==null)System.out.print(p.data);elseSystem.out.print(p.data+"f );p=p.next;}}}(3)建立测试类Test.javappublic class test {public static void main(String[] args) throws Exception { // TODO Auto-generated method stubScanner sc=new Scanner(System.in);boolean or;int xz,xx;System.out.println("请选择插入的方法：0、头插法，1、尾插法");xz=sc.nextInt();if(xz!=0)or=true;elseor=false;System. out.println("请插入的结点的个数：”)；xx=sc.nextInt();LinkList L=new LinkList(xx,or);System.out.println("建立的链表为：");L.display();System.out.println();System.out.println("链表的长度："+L.length());System. out.println(”请输入查找的结点的数据：”)；Object x=sc.next();int position=L.indexOf(x);System.out.println("结点的数据为："+x+"的位置为："+position); System. out.println("请输入删除的结点的位置：”)；int sr=sc.nextInt();L.remove(sr);L.display();System.out.println();System.out.println("链表的长度："+L.length()); }品P rob I em & J a vs d oc / Declaration Q Error Log 里Con sole-M、、■=：termin8ted> test [3] [Java Application] C U &ert\Ad im i n i st rat o r\Ap p Data\L o cs I请选择插入.的方法：0、头插法，lv星插法请插入的特点的个数：请愉入结点的颓据(尾插法)：A B C E D F建立的旌表为；A+B T C+E T D+F链表的长度：6请输入查找的结点的数据:结点的数据为：E的位置为：3请输入删除的结点的位置,R+B T E+DW道表的长度：S方法二(引入get和set方法)Package sy;import java.util.Scanner;//单链表的结点类public class Node {private Object data; //存放结点值private Node next; //后继结点的引用public Node() { //无参数时的构造函数this(null, null);}public Node(Object data) { // 构造值为data 的结点this(data, null);}public Node(Object data, Node next) {//构造值为data 和next 的结点构造函数this.data = data;this.next = next;}public Object getData() { return data;}public void setData(Object data) {this.data = data;}public Node getNext() { return next;public void setNext(Node next) { this.next = next;}}//实现链表的基本操作类public class LinkList {Node head=new Node();//生成一个带头结点的空链表//根据输入的一系列整数，以0标志结束，用头插法建立单链表public void creat() throws Exception {Scanner sc = new Scanner(System.in); //构造用于输入的对象for (int x=sc.nextInt(); x!=0; x=sc.nextInt()) //输入若干个数据元素的值(以0结束) insert(0, x);//生成新结点,插入到表头}//返回带头结点的单链表中第i个结点的数据域的值。