首頁(yè) 猿問(wèn) 以遞歸方式反轉(zhuǎn)Java中的鏈表

以遞歸方式反轉(zhuǎn)Java中的鏈表

Java 算法與數(shù)據(jù)結(jié)構(gòu)

智慧大石 2019-08-14 17:35:37

以遞歸方式反轉(zhuǎn)Java中的鏈表我一直在為一個(gè)類(lèi)的Java項(xiàng)目工作。它是鏈表的實(shí)現(xiàn)（此處稱(chēng)為AddressList包含調(diào)用的簡(jiǎn)單節(jié)點(diǎn)ListNode）。問(wèn)題在于，所有事情都必須通過(guò)遞歸算法來(lái)完成。我能做的一切都很好，沒(méi)有一種方法：public AddressList reverse()ListNode：public class ListNode{ public String data; public ListNode next;}現(xiàn)在我的reverse函數(shù)只調(diào)用一個(gè)輔助函數(shù)，該函數(shù)接受一個(gè)允許遞歸的參數(shù)。public AddressList reverse(){ return new AddressList(this.reverse(this.head));}我的助手功能有簽名private ListNode reverse(ListNode current)。目前，我使用堆棧迭代地工作，但這不是規(guī)范要求的。我在C中找到了一個(gè)遞歸反轉(zhuǎn)的算法，并手工將其轉(zhuǎn)換為Java代碼，但是它有效，但我對(duì)此并不了解。編輯：沒(méi)關(guān)系，我在此期間弄清楚了。private AddressList reverse(ListNode current, AddressList reversedList){ if(current == null) return reversedList; reversedList.addToFront(current.getData()); return this.reverse(current.getNext(), reversedList);}雖然我在這里，有沒(méi)有人看到這條路線有任何問(wèn)題？

查看完整描述

3 回答

慕仙森

TA貢獻(xiàn)1827條經(jīng)驗(yàn) 獲得超8個(gè)贊

一個(gè)回復(fù)中的代碼說(shuō)明了這一點(diǎn)，但是您可能會(huì)發(fā)現(xiàn)通過(guò)詢(xún)問(wèn)和回答微小的問(wèn)題（這是The Little Lisper中的方法）從下往上開(kāi)始更容易：

null的反轉(zhuǎn)是什么（空列表）？空值。
單元素列表的反轉(zhuǎn)是什么？元素。
n元素列表的反轉(zhuǎn)是什么？與列表其余部分相反的是第一個(gè)元素。

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;}

反對(duì) 回復(fù) 2019-08-14

慕斯王

TA貢獻(xiàn)1864條經(jīng)驗(yàn) 獲得超2個(gè)贊

我在接受采訪時(shí)被問(wèn)到這個(gè)問(wèn)題，并且因?yàn)槲矣悬c(diǎn)緊張而感到煩惱。

這應(yīng)該反轉(zhuǎn)一個(gè)單鏈表，用反向調(diào)用（head，NULL）; 所以如果這是你的清單：

1-> 2-> 3-> 4-> 5->空它會(huì)變成：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
    }

編輯：我已經(jīng)完成了6次編輯，顯示它對(duì)我來(lái)說(shuō)仍然有點(diǎn)棘手lol

反對(duì) 回復(fù) 2019-08-14

慕妹3146593

TA貢獻(xiàn)1820條經(jīng)驗(yàn) 獲得超9個(gè)贊

我得到了一半（直到null，并且由plinth建議的一個(gè)節(jié)點(diǎn)），但在進(jìn)行遞歸調(diào)用后失去了軌道。然而，在閱讀了基座的帖子后，我想出了以下內(nèi)容：

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;}

反對(duì) 回復(fù) 2019-08-14