逆置有兩種方法,第一是把所有節(jié)點(diǎn)反過來。還有一種就是改變節(jié)點(diǎn)中的值。
專業(yè)成都網(wǎng)站建設(shè)公司,做排名好的好網(wǎng)站,排在同行前面,為您帶來客戶和效益!創(chuàng)新互聯(lián)公司為您提供成都網(wǎng)站建設(shè),五站合一網(wǎng)站設(shè)計(jì)制作,服務(wù)好的網(wǎng)站設(shè)計(jì)公司,成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作負(fù)責(zé)任的成都網(wǎng)站制作公司!
第一種情況,其實(shí)可以考慮用頭插法,來實(shí)現(xiàn)逆置。
下面的算法是基于頭插法的思想,逆置鏈表的,僅供參考。
LinkList anti_linklist(LinkList demo)
{
LInkList *p,*q;//work pointer
LinkList head;
head=new LinkList();
head-next=null;//init head pointer
p=demo-head-next;//make p points to the first node
if(p==null)
return null;//the linklist is null
while(p!=null)
{
q=p;
q-next=head-next;
head-next=q;
p=p-next;
}
}
我看了好長時(shí)間,終于明白你哪里錯(cuò)了。
1)先說一個(gè)你的程序不是算法問題的錯(cuò)誤,你的鏈表的header里面不應(yīng)該存放具體數(shù)據(jù),也就是說header里面的data應(yīng)該不用。雖然你的outputLink 方法把header里的data也輸出了,但是reverse方法忽略了header里的數(shù)據(jù),而且你不可能創(chuàng)建長度為0的鏈表,因?yàn)槟愕臉?gòu)造方法里面header不管n為多少,都會(huì)有數(shù)據(jù)。
2)reverse里的錯(cuò)誤就是q與p在循環(huán)里是同一個(gè)對(duì)象,q.next就是p.next,循環(huán)第二行q.next=rev.header,因此p.next也是rev.header,所以最后一行p=p.next,p永遠(yuǎn)不會(huì)是null,死循環(huán)。
3)想說一個(gè)不是錯(cuò)誤的問題,不要把java與c弄混,不要把c語言的用法套到j(luò)ava里,比如java里面是不建議在另一個(gè)類中直接調(diào)用其他類的數(shù)據(jù)域的,像你這里header.data,在Link類里調(diào)用Node的data數(shù)據(jù)域,這樣會(huì)出問題,應(yīng)該使用get與set方法。還有最好每個(gè)類都有構(gòu)造方法,Node類也應(yīng)該有一個(gè)。
個(gè)人意見,僅供參考,謝謝。
//函數(shù)名 :trav
//功能 :鏈表逆序
//參數(shù) :鏈表頭指針的指針
//返回值 :成功返回1失敗返回0
//說明 :無
int trav(PNode *head){
PNode p_1,p_2,tmp;
//判斷參數(shù)是否有效
if(*head == NULL)
return 0;
//判斷是否少于兩個(gè)節(jié)點(diǎn)
if((*head)-next == NULL)
return 1;
//處理多余兩個(gè)節(jié)點(diǎn)的情況
p_1 = *head;
p_2 = (*head)-next;
tmp = (*head)-next-next;
do{
p_2-next = p_1;
p_1 = p_2;
p_2 = tmp;
} while (tmp((tmp=tmp-next)||1));
//逆序過后設(shè)置頭指針
(*head)-next = NULL;
*head = p_1;
//逆序完成 返回
return 1;
}
寫了一個(gè) 滿足你要求不?
import myjava.Node;
import myjava.SinglyLinkedList;
import myjava.SeqStack;
public class ReverseLinkedListE extends SinglyLinkedListE {
public ReverseLinkedList(){
super();
}
public void reverse(ReverseLinkedListE list){
SeqStackE stack = new SeqStackE();
NodeE p = this.head ;
while(p != null){
stack.push(p.data);
p = p.next;
}
list.clear();
while(!stack.isEmpty()){
list.add(stack.pop());
}
}
public static void main (String[] args) {
ReverseLinkedListInteger list = new ReverseLinkedListInteger();
for(int i = 1;i 6;i++){
list.add(0,new Integer(i));
}
System.out.println("單列表 "+list.toString());
list.reverse(list);
System.out.println("逆轉(zhuǎn)后 "+list.toString());
}
}
定義一個(gè)LinkedListInteger templist = new LinkedList();來存儲(chǔ)list里面的值,通過迭代list,將值插入在templist的頭上,那么templist就是list的反轉(zhuǎn)了,最后將templist賦值給list就行了!
如下代碼:
public?void?reverse()?{
LinkedListInteger?list?=?new?LinkedList();
LinkedListInteger?templist?=?new?LinkedList();
int?i?=?0;
while?(i??6)?{
list.add(i);
i++;
}
IteratorInteger?it?=?list.iterator();
int?m;
while?(it.hasNext()??i?=?0)?{
m?=?it.next();
templist.addFirst(m);
i--;
}
list?=?templist;
System.out.println(list);
}
運(yùn)行結(jié)果為:
5 4 3 2 1 0
從API中可以看到List等Collection的實(shí)現(xiàn)并沒有同步化,如果在多線程應(yīng)用程序中出現(xiàn)同時(shí)訪問,而且出現(xiàn)修改操作的時(shí)候都要求外部操作同步化;調(diào)用Iterator操作獲得的Iterator對(duì)象在多線程修改Set的時(shí)候也自動(dòng)失效,并拋出java.util.ConcurrentModificationException。這種實(shí)現(xiàn)機(jī)制是fail-fast,對(duì)外部的修改并不能提供任何保證。
Iterator是工作在一個(gè)獨(dú)立的線程中,并且擁有一個(gè) mutex鎖,就是說Iterator在工作的時(shí)候,是不允許被迭代的對(duì)象被改變的。
Iterator被創(chuàng)建的時(shí)候,建立了一個(gè)內(nèi)存索引表(單鏈表),這個(gè)索引表指向原來的對(duì)象,當(dāng)原來的對(duì)象數(shù)量改變的時(shí)候,這個(gè)索引表的內(nèi)容沒有同步改變,所以當(dāng)索引指針往下移動(dòng)的時(shí)候,便找不到要迭代的對(duì)象,于是產(chǎn)生錯(cuò)誤。
List、Set等是動(dòng)態(tài)的,可變對(duì)象數(shù)量的數(shù)據(jù)結(jié)構(gòu),但是Iterator則是單向不可變,只能順序讀取,不能逆序操作的數(shù)據(jù)結(jié)構(gòu),當(dāng) Iterator指向的原始數(shù)據(jù)發(fā)生變化時(shí),Iterator自己就迷失了方向。
所以如果像下面這么寫就會(huì)拋出異常java.util.ConcurrentModificationException
:
public?void?reverse()?{
LinkedListInteger?list?=?new?LinkedList();
int?i?=?0;
while?(i??6)?{
list.add(i);
i++;
}
IteratorInteger?it?=?list.iterator();
int?m;
while?(it.hasNext()??i?=?0)?{
m?=?it.next();
list.add(m);
list.remove(0);
i--;
}
System.out.println(list);
}
初級(jí)java工程師多數(shù)是剛畢業(yè)或者工作1,2年的新人。對(duì)于新人,面試中基礎(chǔ)問題會(huì)問道很多,因?yàn)橄纫疾爝@個(gè)人的基礎(chǔ)。
關(guān)于基礎(chǔ)類的題目,我在面試初級(jí)java工程師的時(shí)候一般會(huì)問下面兩大類問題,每類5個(gè)題目,這樣下來我就基本可以了解這位工程師的程度了。
java基礎(chǔ)類
面向?qū)ο蠡A(chǔ)類
java基礎(chǔ)類
1.描述一下java的訪問修飾符,和它們之間的區(qū)別?
回答:如果可以回到出public,private,protected,就算是ok;回答出default的,加分。
2. int和Integer 區(qū)別?
回答:如果回答出Integer是int的包裝類,就算ok;回答出其他的基本類型和它們相應(yīng)的包裝類,加分。
3.如何定義一個(gè)單精度浮點(diǎn)類型的變量?
回答:float 變量名=1.2f ;回答出不加最后的f為雙精度浮點(diǎn)類型,加分
4. equals和==的區(qū)別?
回答: equals是值比較(一般處理java開發(fā)都會(huì)這么說,算是ok的)而==是引用比較(或者對(duì)象比較);回答equals是可以自定義的,加分
5.將一個(gè)數(shù)組作為參數(shù)傳遞到一個(gè)方法中,在方法中,數(shù)組內(nèi)的元素值被改變了,那么在方法外部,這個(gè)數(shù)組內(nèi)的元素是否也被改編了?
回答:是,因?yàn)閖ava方法中傳遞的是引用,就ok。如果回答中,將引用說明了自己的理解,加分。
面向?qū)ο蠡A(chǔ)類
1.重載和重寫的區(qū)別?
回答:這個(gè)看個(gè)人理解,理解沒有什么大的偏差就ok;回答出多態(tài)相關(guān)的,加分。
2.構(gòu)造方法能不能重載?
回答:可以重載,ok;回答構(gòu)造方法時(shí)不能繼承的,所以如果要調(diào)用指定父類構(gòu)造器就必須重寫子類構(gòu)造方法,加分。
3.抽象方法(abstract)是否可以被final、static、native修飾?
回答:都不可以,因?yàn)槌橄蠓椒ㄊ潜仨氉宇悓?shí)現(xiàn)的,final方法時(shí)不可以被重寫的,static是父類必須實(shí)現(xiàn)的方法,native是本地語言實(shí)現(xiàn)的方法?;卮鸪龇庋b和繼承相關(guān)的,加分
4.當(dāng)父類引用指向子類對(duì)象的時(shí)候,子類重寫了父類方法和屬性,那么當(dāng)訪問屬性的時(shí)候,訪問是誰的屬性?調(diào)用方法時(shí),調(diào)用的是誰的方法?
回答:訪問的是父類的屬性,調(diào)用的是子類的方法,ok;如果可以畫圖解釋的話,加分
5.抽象類和接口有什么異同?
回答:一些類定義上的區(qū)別,ok;回答在應(yīng)用過程中,如何根據(jù)業(yè)務(wù)定義接口,加很多分
最后,如果前面問題回答的不錯(cuò),會(huì)補(bǔ)充兩個(gè)編程習(xí)慣問題。
1.在你寫過的代碼中,你寫過超過2層的循環(huán)嗎,怎么實(shí)現(xiàn)的?
回答:沒有,就算ok;如果回答有,聽一下實(shí)現(xiàn),如果原因說不出來,扣分。
2.在你寫過的代碼中,if語句最多嵌套了幾層,最多有多少分支,怎么實(shí)現(xiàn)的?
回答:3層以下,就算ok;如果回答3層以上,聽一下實(shí)現(xiàn),如果原因說不出來,扣分。
4,5個(gè)分支,就算ok;如果回答5個(gè)分支以上,聽一下實(shí)現(xiàn),如果原因說不出來,扣分。
最后兩個(gè)題其實(shí)比較陷阱,但是正是一個(gè)反向的思考才能了解面試者之前的工作狀態(tài)。
如果面試者在平日里就有好的習(xí)慣,自然不用擔(dān)心。