Java实现单链表的各种操作
程序员文章站
2024-03-11 10:53:49
主要内容:
单链表的基本操作
删除重复数据
找到倒数第k个元素
实现链表的反转
从尾到头输出链表
找到中间节点
检测链表是否有...
主要内容:
- 单链表的基本操作
- 删除重复数据
- 找到倒数第k个元素
- 实现链表的反转
- 从尾到头输出链表
- 找到中间节点
- 检测链表是否有环
- 在不知道头指针的情况下删除指定节点
- 如何判断两个链表是否相交并找出相交节点
直接上代码,就是这么奔放~~~
package pers.ty.$1101datastructure; import java.util.hashtable; /** * @author administrator * 实现单链表的基本操作,增加删除节点、排序、打印、计算长度 */ public class mylinkedlist { node head = null;//链表头的作用 /**向链表中插入数据 * @param d:插入数据的内容 */ public void addnode(int d){ node newnode=new node(d); if(head==null){ head=newnode; return; } node tmp=head; while(tmp.next!=null){ tmp=tmp.next; } //add node to end tmp.next=newnode; } /** * @param index:删除第index个节点 * @return 成功返回true,失败返回false */ public boolean deletenode(int index){ if(index<1||index>length()){ return false;//删除元素位置不合理 } //删除链表中的第一个元素 if(index==1){ head=head.next; return true; } int i=1; node prenode=head; node curnode=prenode.next; while(curnode!=null){ if(i==index){ prenode.next=curnode.next; return true; } prenode=curnode; curnode=curnode.next; i++; } return true; } /** * @return 返回链表的长度length */ public int length(){ int length=0; node tmp=head; while(tmp!=null){ length++; tmp=tmp.next; } return length; } /** * 对链表进行排序 * @return 返回排序后的头结点 */ public node orderlist(){ node nextnode=null; int temp=0; node curnode=head; while(curnode.next!=null){ nextnode=curnode.next; while(nextnode!=null){ if(curnode.data>nextnode.data){ temp=curnode.data; curnode.data=nextnode.data; nextnode.data=temp; } nextnode=nextnode.next; } curnode=curnode.next; } return head; } /** * 打印链表中所有数据 */ public void printlist(){ node tmp=head; while(tmp!=null){ system.out.print(tmp.data+" "); tmp=tmp.next; } system.out.println(); } /** * 从链表中删除数据的第一种方法 * 遍历链表,把遍历到的数据存到一个hashtable中,在遍历过程中若当前访问的值在hashtable * 中存在,则可以删除 * 优点:时间复杂度低 缺点:需要额外的存储空间来保存已访问过得数据 */ public void deleteduplecate1(){ hashtable<integer,integer> table=new hashtable<integer,integer>(); node tmp=head; node pre=null; while (tmp!=null) { if(table.containskey(tmp.data)) pre.next=tmp.next; else{ table.put(tmp.data, 1); pre=tmp; } tmp=tmp.next; } } /** * 从链表中删除重复数据的第二种方法 * 双重循环遍历 * 优缺点很明显 */ public void deleteduplecate2(){ node p=head; while (p!=null) { node q=p; while(q.next!=null){ if(p.data==q.next.data){ q.next=q.next.next; }else{ q=q.next; } } p=p.next; } } /** * @param k:找到链表中倒数第k个节点 * @return 该节点 * 设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点 */ public node findelem(node head,int k){ if(k<1||k>this.length()) return null; node p1=head; node p2=head; for (int i = 0; i < k-1; i++) p2=p2.next; while (p2.next!=null) { p2=p2.next; p1=p1.next; } return p1; } /** * 实现链表的反转 * @param head链表的头节点 */ public void reverseiteratively(node head){ node preversedhead=head; node pnode=head; node pprev=null; while (pnode!=null) { node pnext=pnode.next; if(pnext==null) preversedhead=pnode; pnode.next=pprev; pprev=pnode; pnode=pnext; } this.head=preversedhead; } /** * 通过递归从尾到头输出单链表 * @param head */ public void printlistreversely(node head){ if(head!=null){ printlistreversely(head.next); system.out.print(head.data+" "); } } /** * 查询单链表的中间节点 * 定义两个指针,一个每次走一步,一个每次走两步... * @param head * @return q为中间节点 */ public node searchmid(node head){ node q=head; node p=head; while (p!=null&&p.next!=null&&p.next.next!=null) { q=q.next; p=p.next.next; } return q; } /** * 在不知道头指针的情况下删除指定节点 * 链表尾节点无法删除,因为删除后无法使其前驱节点的next指针置为空 * 其他节点,可以通过交换这个节点与其后继节点的值,然后删除后继节点 * @param n * @return */ public boolean deletenode(node n){ if(n==null||n.next==null) return false; int tmp=n.data; n.data=n.next.data; n.next.data=tmp; n.next=n.next.next; return true; } /** * 判断两个链表是否相交 * 如果两个链表相交,则肯定有相同的尾节点,遍历两个链表,记录尾节点,看是否相同 * @param h1链表1的头节点 * @param h2链表2的头结点 * @return 是否相交 */ public boolean isintersect(node h1,node h2){ if(h1==null||h2==null) return false; node tail1=h1; while (tail1.next!=null){ tail1=tail1.next; } node tail2=h2; while(tail2.next!=null){ tail2=tail2.next; } return tail1==tail2; } /** * 找出相交的第一个节点 * @param h1 * @param h2 * @return */ public node getfirstmeetnode(node h1,node h2){ if(h1==null||h2==null) return null; node tail1=h1; int len1=1; while (tail1.next!=null){ tail1=tail1.next; len1++; } node tail2=h2; int len2=1; while(tail2.next!=null){ tail2=tail2.next; len2++; } if(tail1!=tail2){ return null; } node t1=h1; node t2=h2; //找出较长的链表先遍历 if(len1>len2){ int d=len1-len2; while(d!=0){ t1=t1.next; d--; } } if(len1<len2){ int d=len2-len1; while(d!=0){ t2=t2.next; d--; } } while(t1!=t2){ t1=t1.next; t2=t2.next; } return t1; } public static void main(string[] args) { mylinkedlist list=new mylinkedlist(); } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持!