习题3.写一个算法,假设单链表的表头指针head表示,其类型为LinkList,
写出将其所有节点按相反次序连接的算法
这个算法的效率不高,因为前提是单链表,
所以要重复查找,我想了半天,得出的最优算法是返回最末节点,并删除,
将最末的节点添加到新的链表中,就形成了反转的链表,
如果用双链表的话,效率会有很大的提高.
算法如下:
java 代码
java 代码
- class Node{
- int element;
- Node next;
- public Node(int e){
- this(e,null);
- }
- public Node(int e,Node next){
- this.element=e;
- this.next=next;
- }
- }
- class LinkedList{
- public Node header;
- public LinkedList(){
- header=null;
- }
- public boolean isEmpty() {
- return header == null;
- }
- public void addtotail(int e){
- if (!isEmpty()) {
- Node temp = header.next;
- if (temp == null) {
- header.next = new Node(e);
- } else {
- while (temp.next != null) {
- temp = temp.next;
- }
- temp.next = new Node(e);
- }
- } else {
- header = new Node(e);
- }
- }
- public Node deleteTail(){
- if(!isEmpty()){
- if(header.next!=null){
- Node temp=header;
- Node temp1=header.next;
- while(temp1.next!=null){
- temp1=temp1.next;
- temp=temp.next;
- }
- temp.next=null;
- return temp1;
- }
- else if(header.next==null){
- Node temp=header;
- header=null;
- return temp;
- }
- }
- else{
- System.out.println("This is already a empty list");
- }
- return null;
- }
- public void printAll() {
- for (Node temp = header; temp != null; temp = temp.next) {
- System.out.print(temp.element + " ");
- }
- }
- public void reverse(LinkedList la,LinkedList lb){
- Node temp=null;
- temp=la.deleteTail();
- while(temp!=null){
- lb.addtotail(temp.element);
- temp=la.deleteTail();
- }
- }
- }
- public class Reverse {
- public static void main(String args[]){
- LinkedList La=new LinkedList();
- LinkedList Lb=new LinkedList();
- for(int i=1; i<27; i=i+3){
- La.addtotail(i);
- }
- La.printAll();
- System.out.println();
- Lb.reverse(La, Lb);
- Lb.printAll();
- }
- }
运行结果:
1 4 7 10 13 16 19 22 25
This is already a empty list
25 22 19 16 13 10 7 4 1
分析:
因为将链表La全部删除之后,已经是一个空链表,
所以再调用deleteTail的时候,会打印出This is already a empty list
|