如何递归地在Java中反转链接列表?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (193)

我有一个链表(这里称为AddressList包含简单节点的ListNode实现)。问题在于,我必须用递归算法来完成。

我的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代码,并且它工作运行,但是我不理解

提问于
用户回答回答于
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;
}
用户回答回答于

我在接受采访时被问到了这个问题

你应该颠倒单向链表,用reverse(head,NULL)调用; 所以如果这是你的列表为:

1-> 2-> 3-> 4-> 5>null
它会变成:
5-> 4-> 3-> 2-> 1→null

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

扫码关注云+社区

领取腾讯云代金券