以遞歸方式反轉Java中的鏈表我一直在為一個類的Java項目工作。它是鏈表的實現（此處稱為AddressList包含調用的簡單節點ListNode）。問題在于，所有事情都必須通過遞歸算法來完成。我能做的一切都很好，沒有一種方法：public AddressList reverse()ListNode：public class ListNode{
public String data;
public ListNode next;}現在我的reverse函數只調用一個輔助函數，該函數接受一個允許遞歸的參數。public AddressList reverse(){
return new AddressList(this.reverse(this.head));}我的助手功能有簽名private ListNode reverse(ListNode current)。目前，我使用堆棧迭代地工作，但這不是規范要求的。我在C中找到了一個遞歸反轉的算法，并手工將其轉換為Java代碼，但是它有效，但我對此并不了解。編輯：沒關系，我在此期間弄清楚了。private AddressList reverse(ListNode current, AddressList reversedList){
if(current == null)
return reversedList;
reversedList.addToFront(current.getData());
return this.reverse(current.getNext(), reversedList);}雖然我在這里，有沒有人看到這條路線有任何問題？
3 回答
慕仙森
TA貢獻1827條經驗 獲得超8個贊
一個回復中的代碼說明了這一點，但是您可能會發現通過詢問和回答微小的問題（這是The Little Lisper中的方法）從下往上開始更容易：
null的反轉是什么（空列表）？空值。
單元素列表的反轉是什么？元素。
n元素列表的反轉是什么？與列表其余部分相反的是第一個元素。
public ListNode Reverse(ListNode list){
if (list == null) return null; // first question
if (list.next == null) return list; // second question
// third question - in Lisp this is easy, but we don't have cons
// so we grab the second element (which will be the last after we reverse it)
ListNode secondElem = list.next;
// bug fix - need to unlink list from the rest or you will get a cycle
list.next = null;
// then we reverse everything from the second element on
ListNode reverseRest = Reverse(secondElem);
// then we join the two lists
secondElem.next = list;
return reverseRest;}
慕斯王
TA貢獻1864條經驗 獲得超2個贊
我在接受采訪時被問到這個問題，并且因為我有點緊張而感到煩惱。
這應該反轉一個單鏈表，用反向調用（head，NULL）; 所以如果這是你的清單：
1-> 2-> 3-> 4-> 5->空它會變成：5-> 4-> 3-> 2-> 1->空
//Takes as parameters a node in a linked list, and p, the previous node in that list
//returns the head of the new list
Node reverse(Node n,Node p){
if(n==null) return null;
if(n.next==null){ //if this is the end of the list, then this is the new head
n.next=p;
return n;
}
Node r=reverse(n.next,n); //call reverse for the next node,
//using yourself as the previous node
n.next=p; //Set your next node to be the previous node
return r; //Return the head of the new list
}編輯：我已經完成了6次編輯，顯示它對我來說仍然有點棘手lol
慕妹3146593
TA貢獻1820條經驗 獲得超9個贊
我得到了一半（直到null，并且由plinth建議的一個節點），但在進行遞歸調用后失去了軌道。然而，在閱讀了基座的帖子后，我想出了以下內容：
Node reverse(Node head) {
// if head is null or only one node, it's reverse of itself.
if ( (head==null) || (head.next == null) ) return head;
// reverse the sub-list leaving the head node.
Node reverse = reverse(head.next);
// head.next still points to the last element of reversed sub-list.
// so move the head to end.
head.next.next = head;
// point last node to nil, (get rid of cycles)
head.next = null;
return reverse;}添加回答
舉報
0/150
提交
取消