时间戳

首页 > 解决方案 > 通过在每次递归中将链表分成两半来递归地反转单链表

java - 通过在每次递归中将链表分成两半来递归地反转单链表

问题描述

我如何在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;
}

标签： javaalgorithmlinked-list

解决方案

因为您正在使用链接列表，所以您建议的方法不太可能有效。确定中点的位置是线性时间操作，即使列表的大小已知，您仍然必须迭代到中点。因为您在递归树的每个节点都有一个线性项，所以整体性能将是 O(n lg n)，比您提供的代码的 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 的最后一个元素现在是第一个整体。

推荐阅读