我如何在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;
}
1条答案
按热度按时间u5i3ibmn1#
因为您使用的是链表,所以您建议的方法不太可能有效。确定中点的位置是一个线性时间操作,即使列表的大小已知,也必须迭代到中点。因为在递归树的每个节点上都有一个线性项,所以总体性能将是o(nlgn),比您提供的代码的o(n)界慢。
也就是说,您仍然可以通过以下策略来反转列表:
你可以看到,首先,我们的列表是ab,然后我们递归得到a'和b',每一个都是半列表的反向版本。然后输出新的反向列表b'a'。原始a的第一个元素现在是列表整体的最后一个元素,原始b的最后一个元素现在是列表整体的第一个元素。