链表逆序的Java实现代码

OPEN930719 贡献于2013-11-11

作者 lenovo  创建于2013-10-28 12:48:00   修改者lenovo  修改于2013-10-28 14:05:00字数2198

文档摘要:算法思路:将单链表中各结点的next域改为指向其前驱结点,设p指向链表中的某个结点,front指向p的前驱结点,逆转过程会使p.next原本指向后继结点的链断开,所以在断开之前要用rear存放p的后继结点。
关键词:

算法思路:将单链表中各结点的next域改为指向其前驱结点,设p指向链表中的某个结点,front指向p的前驱结点,逆转过程会使p.next原本指向后继结点的链断开,所以在断开之前要用rear存放p的后继结点。 程序代码如下: 1.LinkedListReverse.java: package xqy; import java.util.LinkedList; public class LinkedListReverse { public static void reverse(SinglyLinkedList list){ Node p=list.head.next,front=null,rear=null; //在循环中,front、p、rear各向后移动一个结点,循环完成时完成逆序 while(p!=null){ rear=p.next; //设置rear为p结点的后继结点 p.next=front; //使p.next指向p的前驱结点front front=p; p=rear; } list.head.next=front; } public static void main(String args[]){ String values[]={"刘","马","张","熊"}; SinglyLinkedList list=new SinglyLinkedList(values); System.out.println("原链表为:"+list.toString()); reverse(list); System.out.println("链表倒置后为:"+list.toString()); } } 2.SinglyLinkedList.java: //带头结点的单链表类,实现线性表接口 public class SinglyLinkedList implements LList { //头指针,指向单链表的头结点 protected Node head; //默认构造法方法,构造空的单链表。 public SinglyLinkedList(){this.head=new Node();}; public SinglyLinkedList(T[] element) { this(); Node rear=this.head; for(int i=0;i(element[i],null); rear=rear.next; } } public boolean isEmpty(){ return this.head.next==null;} //判断单链表是否为空 public int length() //返回单链表长度 { int i=0; Node p=this.head.next; while(p!=null) { i++; p=p.next; } return i; } //返回单链表所有元素的描述字符串,形式为“(,)”,覆盖Object类的toString()方法 public String toString(){ String str="("; Node p=this.head.next; while(p!=null) { str+=p.data.toString(); if(p.next!=null) str+=","; p=p.next; } return str+")"; } } 3.Node.java: //单链表结点类,泛型参数T表示数据元素的数据类型 public class Node { public T data; public Node next; public Node(T data,Node next){ this.data=data; this.next=next; } public Node(){ this(null,null); } } 4.LList.java: //线性表接口,泛型参数T表示数据元素的数据类型 public interface LList { boolean isEmpty(); int length(); } 程序运行结果截图: 算法复杂性分析: 时间复杂度:时间主要花在从原链表头走到最后,循环中每一次都是front、p、rear三个结点的引用同时沿单链表向后移动,这样通过一次遍历旧链表就可以完成链表的逆转,复杂度与链表长度成正比,为O(n)。 空间复杂度:要同时给三个结点的引用分配出空间,所以空间复杂度为O(3)=O(1); 小组问题: 看教材的时候有很多例题会写出这样的程序语句,比如顺序表类中就有“public class SeqList implements LList”,在单链表的插入中也有Node这样的语句,出现频率极高说明这是一个比较重要的用法,但 让我搞不懂的地方是,为什么static后面会有一个这个东西,这个东西到底应该怎么用。 后来去查了很多资料,原来这就是泛型方法。如果没有这个的定义,在后面参数中使用泛型就会报错。我们可以通过允许指定泛型类或方法操作的类型,泛型这种格式用法将类型安全的任务转移给了编译器,让编译器来负责这项工作,而不需要我们自己编写代码来测试数据类型是否正确,因为在编译时会强制使用正确的数据类型,这样就减少了类型强制转换的需要和运行时错误的可能性。而且泛型方法提供了类型安全但却没有增加多个实现的开销,很实用。

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 1 人已下载

下载文档