這篇文章主要介紹了Java語言實作反轉鍊錶程式碼範例,小編覺得挺不錯的,這裡分享給大家,供需要的朋友參考。
問題描述
定義一個函數,輸入一個鍊錶的頭結點,反轉該鍊錶並輸出反轉後的鍊錶的頭結點。鍊錶結點如下:
public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }
想法1:
要想反轉鍊錶,對於結點i,我們要把它的next指向它的前趨,因此我們需要保存前趨結點,同時,如果我們已經把i的next重新賦值,會無法找到i的後繼,因此,在重新賦值之前,我們要保存i的後繼。
程式碼:
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:
使用遞迴的想法(暫時沒有想到,因為如果用遞歸的話,每次應該是:鍊錶的第一個結點<—遞歸返回的鍊錶的尾指針,但是這樣的話就無法獲得反轉後的頭指針了。
總結
#以上是Java實作反轉鍊錶的程式碼範例的詳細內容。更多資訊請關注PHP中文網其他相關文章!