JAVA、一方向チェーンの逆転を実現
2739 ワード
《一方向チェーン逆転》
最近面接をしています.就職活動はAndroidの応用方向の仕事です.基礎知識は大丈夫ですが、アルゴリズムは大丈夫です.携帯電話のクライアントをするのは基本的にアルゴリズムが多くなく、アーキテクチャ設計、結合、機能最適化、UI、IOなどが多い.もういいです.余計なことを言わないでください.本題に入ります
片方向リンク表はわかります.これ以上説明を多くしません.一方向チェーンの反転、時間複雑度、空間複雑度が低い方が良いアルゴリズムですか?基本的にはO(n)を実行しています.3つの引用pre、cur、tempNext、pre、curはそれぞれ第一の要素と第二の要素を指します.tempNextは第三の要素の参照を保存します.反転前の2つ、p 2-->p 1(この時p 2.nextが切断されていることに注意してください.)は、本来は第2の参照を指すべきです.pre、curはp 2、p 3に移動します.つまりpre参照p 2、curはp 3を参照します.最初のpre、curはp 1、p 2をそれぞれ指します.このように往復します.
注意すべき点は何ですか?
1自身のJAVAコードは、Javaが値伝達なのか、それとも引用伝達なのかに注意が必要です.注意しないと変数交換に問題があります.本当です
2各種臨時変数の記録.目まいしないでください.同時に気をつけます.
コードをかける!自分で書いたものが実行できます.
最近面接をしています.就職活動はAndroidの応用方向の仕事です.基礎知識は大丈夫ですが、アルゴリズムは大丈夫です.携帯電話のクライアントをするのは基本的にアルゴリズムが多くなく、アーキテクチャ設計、結合、機能最適化、UI、IOなどが多い.もういいです.余計なことを言わないでください.本題に入ります
片方向リンク表はわかります.これ以上説明を多くしません.一方向チェーンの反転、時間複雑度、空間複雑度が低い方が良いアルゴリズムですか?基本的にはO(n)を実行しています.3つの引用pre、cur、tempNext、pre、curはそれぞれ第一の要素と第二の要素を指します.tempNextは第三の要素の参照を保存します.反転前の2つ、p 2-->p 1(この時p 2.nextが切断されていることに注意してください.)は、本来は第2の参照を指すべきです.pre、curはp 2、p 3に移動します.つまりpre参照p 2、curはp 3を参照します.最初のpre、curはp 1、p 2をそれぞれ指します.このように往復します.
注意すべき点は何ですか?
1自身のJAVAコードは、Javaが値伝達なのか、それとも引用伝達なのかに注意が必要です.注意しないと変数交換に問題があります.本当です
2各種臨時変数の記録.目まいしないでください.同時に気をつけます.
コードをかける!自分で書いたものが実行できます.
package com.main;
public class Main {
public static void main(String[] args) {
String [] str={"11","2","45","67","23","44","55","89","74","10"};
RevertListfromHead rl= new RevertListfromHead(str);
}
}
package com.main;
public class RevertListfromHead {
public RevertListfromHead(String[] str) {
MyLinkList mList = new MyLinkList(str);
mList.printList(mList.head);
System.out.println("--------------------------");
System.out.println("after revert list is ");
mList.head=mList.revertLinkedList(mList.head);
mList.printList(mList.head);
}
class MyLinkList {
private Node head;
private int mlength;
public MyLinkList(String[] str) {
head = new Node(str[0]);
Node currentNode = head;
for (int i = 1; i < str.length; i++) {
currentNode.next = new Node(str[i]);
currentNode = currentNode.next;
}
mlength = str.length;
}
public Node revertLinkedList(Node _head) {
int sum=0;
if (null == _head) {
return head;
}
Node pre = _head;
Node cur = _head.next;
Node tempnext;
while (null != cur) {
tempnext = cur.next;
cur.next=pre;
pre = cur;
cur = tempnext;
sum++;
}
// null， head
head.next=null;
head = pre;
return head;
}
public void printList(Node _head) {
Node tempNode = _head;
while (tempNode != null) {
System.out.println("current data is : " + tempNode.data);
tempNode = tempNode.next;
}
}
}
static class Node {
String data;
Node next;
public Node(String _data) {
this.data = _data;
}
}
}
・