java鏈表反轉

❶ c語言，鏈表的反轉，請寫出代碼，並講解下，謝了！！！！！

扣著的是頭節點（頭子）

車是首節點（首子）

馬是次節點（次子）

牙簽細的是指針指向，香頭發黑的是指向，鐵頭細的是指向。

根據步驟寫程序的偽演算法（3步4循環，7張圖片搞定），如下：

第一個循環把馬弄到車前面，

第二個循環把相弄到馬前面

第三個循環把士弄到相前面

........

直到香指向為空後停止循環。

代碼如下：只需要一個首結點pHead,就能把鏈表找到，並倒置。具體代碼如下

p香=pHead->pNext;

p鐵=p香->pNext;

p香->pNext=NULL;

P香=p鐵

while(p香 ！=NULL)

{

p鐵=p香->pNext;

p香->pNext=pHead->pNext;

pHead->pNext=p香；

p香=p鐵；

}

對照偽演算法（三步四循環），和上面的代碼是一一對應的：

第一步：香頭指向首子，鐵頭指向次子

第二步：刪掉首子指向次子（鐵頭所指向的那個子）的牙簽

第三步：香頭跟著鐵頭

以下循環條件：（條件：香頭指向不為空）

{

循環1：鐵頭移動到香頭的下一個指向

循環2：香頭的下一個指向首子

循環3：頭子的下一個跟著香頭

循環4：香頭跟著鐵頭

}

自己用道具操作幾遍，然後把流程背會，以後自己根據流程寫代碼即可。

❷ java HashMap擴容的時候，為什麼要把Entry鏈表反轉

我覺得應該是效率問題，如何不做反轉在重新計算hash值後將要獲得當前鏈表的最後一個元素，然後對最後一個元素的next屬性添加一個節點信息，但是如果反轉的話就不用了。

例子：

voidtransfer(Entry[]newTable,booleanrehash){
intnewCapacity=newTable.length;
for(Entry<K,V>e:table){
while(null!=e){
Entry<K,V>next=e.next;
//重新計算hash值
if(rehash){
e.hash=null==e.key?0:hash(e.key);
}
inti=indexFor(e.hash,newCapacity);
//這個是反轉的寫法start
e.next=newTable[i];
newTable[i]=e;
e=next;
激鏈//反轉end
//這個是不反轉的寫法start

Entry<K,V>newEntry=newTable[i];
e.next=null;
if(newEntry!=null){

明者孫while(true){
if(newEntry.next==null){
newEntry.next=e;
break;
}

newEntry=newEntry.next;
}
}else{
newTable[i]=e;
嫌粗}

e=next;
//不反轉end

}
}
}

❸ Java和Rust在實現多線程編程時的異同

Java的實現
打開Follower.java里的這個函數

這里的Follower.this.invitations就是我們的消息隊列，定義是：private LinkedList<Invitation> invitations;LinkedList不是線性安全的集合，需要我們加同步。具體的同步方法就是函數里寫的，通過Java常見的用wait，notify和notifyall給對象加鎖。
處理並發有wait、notify和notiyall，有興趣的朋友可以去這里了解一下：http://www.importnew.com/16453.html。Follower就是一個等待leader發送invitation，處理並返回結果的過程。
Leader.java
這么一段代碼：

裡面就是Leader發送邀請inv，並等待follower返回結果的大概邏輯，通過對消息體加鎖，是Java傳統的實現多線程並發的方式。還有消費者的消息隊列也會加鎖，在Java里，有個對象叫LinkedBlockingQueue，是不用加鎖就可以put和take的，但在例子里，我們選用了更簡單的LinkedList，也是為了表現一下加鎖的邏輯。
Rust的實現
Leader的結構為：

Follower的結構為：

對於其他語言轉過來的同學，這里的Vec，i32，bool都很好理解，不過裡面出現的Arc和Mutex，Sender，Receiver就是新東西了，上面這4個都是Rust標准庫的東西，也是這次分享要介紹的重點對象，是這4個東西共同實現了消息的生產，傳遞和消費。
下面簡單介紹一下分別是做什麼用的：
Arc<T>實現了sync介面。Sync介面是做什麼呢？權威資料是這么說的：當一個類型T實現了Sync，它向編譯器表明這個類型在多線程並發時沒有導致內存不安全的可能性。
如果看不懂不要緊，我們先看看實際中是怎麼用的：

在這個例子里，我們關注這幾句：
let data = Arc::new(Mutex::new(vec![1u32, 2, 3]));
let data = data.clone();
let mut data = data.lock().unwrap();
下面分別解釋一下是做什麼的：
簡單的說Arc::new表明了這是通過clone()方法來使用的，每clone，都會給該對象原子計數+1，通過引用計數的方法來保證對象只要還被其中任何一個線程引用就不會被釋放掉，從而保證了前面說的：這個類型在多線程並發時沒有導致內存不安全的可能性。
如果我們不定義為Arc<>就傳到其他線程使用，編譯器會報：
error: capture of moved value: `data`
data[i] += 1;
我們可以記住clone()就是Arc的用法。
接下來我們看Mutex：
Mutex實現了send介面。同樣，在權威資料里是這么描述的：這個類型的所有權可以在線程間安全的轉移
那我們又是怎麼用Mutex的呢？就是用lock().unwrap()。lock()的作用是獲取對象，如果當前有其他線程正在使用Mutex<T>裡面的T對象時，本線程就會阻塞，從而保證同時只有一個線程來訪問對象，mutex也另外提供了try_lock()的方法，是不阻塞的，只要其他線程被佔用，就返回err，通常Arc和Mutex都是一起使用的。
回到我最原始的題目，Mutex和Arc實現了對象本身的線程共享，但是在線程間如何傳遞這個對象呢？就是靠channel，channel通常是這么定義的let (tx, rx) = mpsc::channel();它會返回兩個對象tx和rx，就是之前我提到的sender和receiver。
在我的Rust實現里，關鍵的語句是以下幾個：
let leaders = (0..leader_cnt).map(|i|
Arc::new(Mutex::new(Leader::new(i,dance_types.len() as i32)))
).collect::<Vec<_>>();
這一句是new一堆leader出來，Arc和Mutex表明leader是可以多線程共享和訪問的。
同樣Follower也是：
let followers = (0..follower_cnt).map(|i|
Arc::new(Mutex::new(Follower::new(i,dance_types.len() as i32,leader_cnt)))
).collect::<Vec<_>>();
接下來這幾句就有點不好理解了。

這里定義了一堆的sender和receiver，其中把他們都作為leader和follower的成員變數存起來。大概意思就是每一個leader都通過sender列表可以發送invitation給所有follower，同時又有單個receiver來接受所有follower發給自己的處理結果inviresult。
同樣follower也是這么做。這樣在之後每一個follower和leader作為一個線程跑起來之後，都能在相互之間建立了一條通信的通道。
這個是和Java實現多線程並發最大的不同之處！Java是通過給對象加鎖，Rust是通過channel轉移對象的所有權，在代碼里，leader發送inv給folloer是下面這一句
match self.senders[*follower_id as usize].lock().unwrap().send(inv){，其中的lock().unwrap()是獲得該leader對該follower的發送通道的所有權，send(inv)就是轉移具體的發送對象invitation所有權了。
這個轉移按照我的理解，應該是內存拷貝。就是在follower接收的時候，let inv = match self.receiver.recv() { ，原來leader裡面的inv在send之後已經是不可訪問了，如果你之後再次訪問了inv，會報use of moved value錯誤，而follower裡面的inv則是在follower的棧里新生成的對象，所以，在Java裡面我只定義了invitation對象，但是在Rust裡面，我要再定義一個InviResult，因為我即使在follower線程裡面填了result欄位，leader線程也不能繼續訪問inv了。所以需要依靠follower再次發送一個invresult給leader，所以整個Rust程序大概就是這么一個思路。
實踐總結
之前我測試比較Java和Rust實現的性能時，由於沒有把調試信息去掉，導致Java比Rust慢很多，特別是那些調試信息都是調用String.format，這是比幾個string相加慢上10倍的方法，兩者都去掉調試信息後，leader和follower都會2000的時候，在我低端外星人筆記本里，性能差別大概是2倍吧，沒我想像中大，Rust的程序整個寫下來比較費力，一方面是對ownership機制不熟，思維沒有轉變過來，另一方面Rust的確需要開發者分部分精力到語法細節上。
編者註：馮總也有一些其它的實踐體會，請參見CSDN對馮耀明的專訪，請戳這里。也可以查看他的個人博客里的總結。
下面摘錄采訪中關於Rust的內容過來：
首先Rust裡面的ownership和lifetime概念真的很酷，就因為這個概念實現無內存泄露，野指針和安全並發。
其次，Rust的語法不簡單，也是有不少坑的，據說Rust的潛在用戶應該是現在的C和C++程序員，他們可能會覺得比較習慣，說不定還 覺得更簡單。由於ownership機制，一些在其他語言能夠跑通的程序在Rust下就要調整實現了，它會改變你寫程序的思維方式。據說一些寫Rust超 過半年的程序員已經愛上它了！
我對Rust感受較深的是下面幾點：
初學者不熟悉ownership機制，會無數次編譯失敗。但一旦編譯成功，那麼程序只剩下邏輯錯誤了。同樣，由於ownership機制，將來在項目里修改Rust代碼將可能是痛苦的過程，因為原來編譯通過的代碼可能加入新功能就編譯不過了，這是我的猜測。
Rust編譯速度慢，不過據說最近每一個Rust新發布的版本編譯速度都比之前的版本提高了30%。
Rust沒有類，有的是結構體加方法，我喜歡這種簡單的概念。
Rust沒有類繼承，只有介面，雖然介面可以提供默認的實現。這樣一來，在大型項目里原來類繼承來重用代碼的效果是否就要用成員變數實例來完成呢？
Rust沒有null，取而代之的是None和Option<T>，也因此，結構體在初始化的時候必須初始化所有欄位。
Rust有我一直很想要的錯誤值返回機制，而不必通過拋異常或者需要每每定義包含結果和錯誤體實現。
Rust用send和sync兩個介面來處理多線程並發，其中Arc<T>和Mutex<T>分別實現了這兩個介面，簡單易用。
Rust目前沒有一個強大的IDE，支持斷點調試，變數監控等。
它跟現在動態語言是兩個截然不同的方向，它適合一些資深的程序員，我倒是覺得有必要有這么一本書，叫《從C++到Rust，你需要改善的20個編程 習慣》，能從實踐上告訴開發者Rust里我們應該遵從什麼樣的編程習慣。Rust未來是否像C那樣流行開來成為新一代的主流語言沒有人能夠知道，但它絕對 是值得你去了解和關注的語言。
進一步的思考：反轉鏈表 - Java和Rust的不同實現
Rust的list應該怎麼定義，譬如反轉列表又是怎麼做呢？
由於ownership的機制和不存在空指針的情況，很多在其他帶GC的語言能夠跑起來的程序在Rust下面就要換一種做法。最近試用Rust的基礎數據結構時，更加加強了我的看法。下面以最原始的鏈表list為例。
在Java中，考慮最基本的鏈表定義
class ListNode {
int val;
ListNode next;

ListNode(int x) {
val = x;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
sb.append(val);
ListNode pNext = this.next;
while (pNext != null) {
sb.append(",");
sb.append(pNext.val);
pNext = pNext.next;
}
sb.append("]");
return String.format("%s", sb.toString());
}
}
如果我們要反轉鏈表，可以這么做：
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode pNext = head.next;
ListNode pPrevious = null;
while (head != null) {
pNext = head.next;
head.next = pPrevious;
pPrevious = head;
head = pNext;
}
return pPrevious;
}
那如果我們按照一般思維，在Rust里對應的實現就是這樣子的：
struct ListNode{
id :i32,
next :Option<Box<ListNode>>
}
反轉鏈表：
fn reverseList2(head :&mut Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match *head{
None => None,
Some(head) => {
let mut head = Some(head);
let mut pNext = head.unwrap().next;
let mut pPrevious:Option<Box<ListNode>> = None;
while true {
match head {
None =>{break;}
_ =>{}
}
pNext = head.unwrap().next;
head.unwrap().next = pPrevious;
pPrevious = head;
head = pNext;
}
pPrevious
}
}
}
然後編譯，報了以下錯誤：
=》match *head{

ERROR：cannot move out of borrowed content
=》 pNext = head.unwrap().next;
ERROR：cuse of moved value: `head`

這些錯誤就是因為Rust的ownership機制，讓我們無法像Java或者C++里保存臨時變數，特別是在循環里。反復試過各種寫法，都行不通。
最後，換成這么來做
鏈表定義：
use List::*;

enum List {
Cons1(i32, Box<List>),
Nil,
}

// Methods can be attached to an enum
impl List {
#[inline]
fn new() -> List {
Nil
}

#[inline]
fn prepend(self, elem: i32) -> List {
Cons1(elem, Box::new(self))
}

fn len(&self) -> i32 {
match *self {
Cons1(_, ref tail) => 1 + tail.len(),
Nil => 0
}
}

fn stringify(&self) -> String {
match *self {
Cons1(head, ref tail) => {
format!("{}, {}", head, tail.stringify())
},
Nil => {
format!("Nil")
},
}
}
}

fn reverseList(list:List, acc:List ) -> List{
match list{
Cons1(val,tail) => {
reverseList(*tail,acc.prepend(val))
}
Nil => acc
}
}

fn main() {
let mut head = List::new();
let mut i=0;
while i < 10 {
i+=1;
head = head.prepend(i);
}
println!("{:30}",head.stringify());
let result = List::new();
let result = reverseList(head,result);
<span style="white-space:pre"> </span>println!("{:30}",result.stringify());
}
從結果可以看到，鏈表已經實現反轉了。所以在Rust下面，很多做法都要換一下。有人說這就是Rust函數式編程的思維。我但願這種遞歸式的做法不會有溢出。

❹ java linked list里的元素順序反過來

定義一個LinkedList<Integer> templist = new LinkedList<>();來存儲list裡面的值，通過迭代list，將值插入在templist的頭上，那麼templist就是list的反轉了，最後將templist賦值給list就行了！

如下代碼：

publicvoidreverse(){
LinkedList<Integer>list=newLinkedList<>();
LinkedList<Integer>templist=newLinkedList<>();
inti=0;
while(i<6){
list.add(i);
i++;
}
Iterator<Integer>it=list.iterator();
intm;
while(it.hasNext()&&i>=0){
m=it.next();
templist.addFirst(m);
i--;
}
list=templist;
System.out.println(list);
}

運行結果為：

5 4 3 2 1 0

從API中可以看到List等Collection的實現並沒有同步化，如果在多線程應用程序中出現同時訪問，而且出現修改操作的時候都要求外部操作同步化；調用Iterator操作獲得的Iterator對象在多線程修改Set的時候也自動失效，並拋出java.util.。這種實現機制是fail-fast，對外部的修改並不能提供任何保證。

Iterator是工作在一個獨立的線程中，並且擁有一個 mutex鎖，就是說Iterator在工作的時候，是不允許被迭代的對象被改變的。

Iterator被創建的時候，建立了一個內存索引表（單鏈表），這個索引表指向原來的對象，當原來的對象數量改變的時候，這個索引表的內容沒有同步改變，所以當索引指針往下移動的時候，便找不到要迭代的對象，於是產生錯誤。

List、Set等是動態的，可變對象數量的數據結構，但是Iterator則是單向不可變，只能順序讀取，不能逆序操作的數據結構，當 Iterator指向的原始數據發生變化時，Iterator自己就迷失了方向。

所以如果像下面這么寫就會拋出異常java.util.

：

publicvoidreverse(){
LinkedList<Integer>list=newLinkedList<>();
inti=0;
while(i<6){
list.add(i);
i++;
}
Iterator<Integer>it=list.iterator();
intm;
while(it.hasNext()&&i>=0){
m=it.next();
list.add(m);
list.remove(0);
i--;
}
System.out.println(list);
}

❺ java反轉鏈表 大神給我添加個注釋好么，我自己研究

publicclassLinktest{
//反轉方法，傳入一個鏈表
publicstaticLinkNodereversal(LinkNodelist){
//pre用來存放前一個鏈表節點
LinkNodepre=list;
//取出下一個鏈表節點,cru用來存放當前鏈表節點
LinkNodecru=list.getNext();
//next用來存放下一個鏈表節點
LinkNodenext;
//如果當前節點不為空(這里意思是如果傳進來的list有下一個節點就繼續執行)
while(null!=cru){
//取出當前節點的下一個節點
next=cru.getNext();
//把前一個節點賦予當前節點的下一個節點(這里產生實際改變)
cru.setNext(pre);
//把當前節點變數賦予前一個節點的變數
pre=cru;
//把下一個節點變數賦予當前
cru=next;
}
//循環體內會循環到方法傳入的LinkNode沒有前一個節點為止
//因為幾次交換的原因

//因為循環結束,所以把next賦空
list.setNext(null);
//因為循環的原因,前一個節點實際是第一個節點
list=pre;
//返回第一個節點
returnlist;
}
publicstaticvoidmain(String[]args){
LinkNodehead=newLinkNode(0);
LinkNodetmp=null;
LinkNodecur=null;
for(inti=1;i<10;i++){
tmp=newLinkNode(i);
if(1==i){
head.setNext(tmp);
}else{
cur.setNext(tmp);
}
cur=tmp;
}
LinkNodeh=head;
while(null!=h){
System.out.print(h.getVal()轎激+"");
h=h.getNext();
梁帆賀}
head=reversal(head);
橡派System.out.println("
**************************");
//列印反轉後的結果
while(null!=head){
System.out.print(head.getVal()+"");
head=head.getNext();
}
}
}