通过在每次递归中将链表一分为二，递归地反转单个链表

Question

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

Answer 1

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