java—通过在每个循环中将链表一分为二来递归地反转单个链表

gpnt7bae  于 2021-07-03  发布在  Java
关注(0)|答案(1)|浏览(365)

我如何在java中编写一个函数,通过将一个单链表分成两半来反转它,这意味着(n/2)个节点是第一部分,其余的是第二部分(n是喜欢的列表的大小),直到它到达一个节点,然后合并这个被分割的部分。允许在每个除法中使用两个新的链表,但不允许使用列表节点。函数必须为void,并且没有函数的参数。我有n,主链表的头和尾。
我在网站上找到了这段代码,但它并没有将链表一分为二,所以没有任何帮助。

static ListNode reverseR(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode first = head;
    ListNode rest = head.next;

    // reverse the rest of the list recursively
    head = reverseR(rest);

    // fix the first node after recursion
    first.next.next = first;
    first.next = null;

    return head;
}
u5i3ibmn

u5i3ibmn1#

因为您使用的是链表,所以您建议的方法不太可能有效。确定中点的位置是一个线性时间操作,即使列表的大小已知,也必须迭代到中点。因为在递归树的每个节点上都有一个线性项,所以总体性能将是o(nlgn),比您提供的代码的o(n)界慢。
也就是说,您仍然可以通过以下策略来反转列表:

Step 1: Split the list L into A (the first half) and B (the second half).
 Step 2: Recurse on each of A and B. This recursion should bottom out 
         when given a list of length 1.
 Step 3: Attach the new head of the reversed A to the new tail of the reversed B.

你可以看到,首先,我们的列表是ab,然后我们递归得到a'和b',每一个都是半列表的反向版本。然后输出新的反向列表b'a'。原始a的第一个元素现在是列表整体的最后一个元素,原始b的最后一个元素现在是列表整体的第一个元素。

相关问题