圖示詳解反轉單連結清單

1、反轉一個單連結清單

解法：可以采用循環和遞歸兩種方式解決，這裡用循環實作

eg：如下有一個連結清單

反轉之後：

分析：首先觀察一下反轉前後的連結清單，新的頭變成了原連結清單的尾節點，這個過程也就是

指向由

變成了

可以發現出現變化的是：整個連結清單的頭節點和next域，原連結清單中888節點的next域儲存的是001節點的位址，反轉後001節點的next域儲存了888節點的位址值，不斷重複這個操作，并且原頭節點888的next域變成了null。

思路：首先定義一個變量cur周遊連結清單，并且這個cur始終指向目前要反轉的這個節點，因為反轉的過程就是讓目前節點的next域指向他的前驅，是以我們需要再定義一個變量指向目前要反轉節點的前驅，當這個cur要反轉後，他的下一個節點就更新了，我們無從得知原連結清單中這個cur的下一個節點，是以，必須要再定義一個變量curNext來記錄目前反轉節點的下一節點。最後要考慮的就是周遊的終止條件和反轉後連結清單的頭的問題了。

詳細步驟：

• 定義四個變量

  cur (周遊連結清單，并且永遠指向目前要反轉的節點)

  prev (反轉後連結清單的臨時的頭，cur指向原連結清單頭，此時還沒有反轉是以prev初始化為null)

  newHead (從語義來看，新連結清單還沒生成此時他的初始化值為null)

  curNext (這個的定義一定首先考慮到他的出現可能會帶來的空指針異常的問題)

• 周遊連結清單，循環的條件就是(cur != null),為了防止curNext空指針異常，我們把他定義在循環裡面，cur不為空，那麼他的next就是curNext節點就不會出現空指針異常的情況。

  cur在周遊中每走一個節點我們都要考慮到他是不是最後一個，如果是，那麼目前節點就是新的頭，将此時的cur置為newHead。

• 反轉節點，此時不要忘記頭節點也是要反轉的，他反轉之後就變成了尾節點，每次完成了一次反轉後cur和prev都是要更新的(始終讓cur指向目前要反轉的節點，prev作為一個臨時的頭指向反轉後的連結清單)

cur.next = prev;
prev = cur;
cur = curNext;
           

java源代碼

public Node reverse() {    
    Node prev = null;    
    Node cur = this.head;
    Node newHead = null;    
while (cur != null) {
    Node curNext = cur.next;       
	if (curNext == null) {           
    	newHead = cur;       
	}        
	cur.next = prev;        
	prev = cur;       
	cur = curNext;         
}    
return newHead;