問題描述
定義一個函數(shù)，輸入一個鏈表的頭結(jié)點(diǎn)，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后的鏈表的頭結(jié)點(diǎn)。鏈表結(jié)點(diǎn)如下：
java" id="highlighter_142911">
|
1
2
3
4
5
6
7
|
public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }} |
思路1：
要想反轉(zhuǎn)鏈表，對于結(jié)點(diǎn)i，我們要把它的next指向它的前趨，因此我們需要保存前趨結(jié)點(diǎn)，同時，如果我們已經(jīng)把i的next重新賦值，會無法找到i的后繼，因此，在重新賦值之前，我們要保存i的后繼。
代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public ListNode ReverseList(ListNode head) { if(head == null){ return null; } ListNode rHead = null; ListNode prior = null;//store prior ListNode q = head;//store current while(q != null){ ListNode next = q.next;//store the next if(next == null){ rHead = q; } q.next = prior; prior = q; q = next; } return rHead; } |
思路2：
使用遞歸的思想（暫時沒有想到，因?yàn)槿绻眠f歸的話，每次應(yīng)該是：鏈表的第一個結(jié)點(diǎn)<—遞歸返回的鏈表的尾指針，但是這樣的話就無法獲得反轉(zhuǎn)后的頭指針了。）后面再思考吧。
總結(jié)
以上就是本文關(guān)于Java語言實(shí)現(xiàn)反轉(zhuǎn)鏈表代碼示例的全部內(nèi)容，希望對大家有所幫助。如有不足之處，歡迎留言指出。
原文鏈接：http://blog.csdn.net/lilianforever/article/details/51839810
