Burton右耳后面好像破了，但是他不让我们看# pets - 心有所宠
a*0
1 楼
我本来用递归方法 但是超时了 本身代码没错 就是慢 为什么慢 因为在每个递归函数
中有O（n）的操作 这样n次递归导致总体O（n平方）
如果坚持递归方法 需要返回调整好的list的尾节点的下一个节点 这个是从网友那里学
来的 其实这个过程有点tricky 为什么不简单返回 list的头节点或者尾节点 而要返
回尾节点的下一个节点呢？ 思路是这样的 尾节点经过调整已经不是原来的尾节点了
它指向的下一个已经不是原来的顺序 那为什么不返回头节点呢 ？ 头节点其实不需要
返回 每次用next找就可以了 而且每次拿到头节点也不好用 必须多次next找到尾节点
又超时了
网友的方法 我改编成了java的 后边也有返回尾节点的方法
但是很容易出错 如果面试 还是用循环而不是递归的方法 当然面试无法检查是不是超
时 所以用我最早的方法也可以吧
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if(head == null)
return;
ListNode scanner = head;
int length =0;
while(scanner != null){
length++;
scanner = scanner.next;
}
reorderHelper(head, length);
}
// helper returns the very last node's next node
public ListNode reorderHelper(ListNode start, int range){
if(range ==0)
return null;
ListNode result = null;
// range == 1 and range ==2 cases don't need adjustment
if(range ==1){
result = start.next;
start.next = null;
return result;
}
if(range ==2){
result = start.next.next;
start.next.next = null;
return result;
}
ListNode temp = reorderHelper(start.next, range -2);
result = temp.next;
temp.next = start.next;
start.next = temp;
return result;
}
}
但是我想如果一定要返回尾节点如何 我也找到了答案 但是返回值仅仅用于存储其下一
个节点
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if(head == null)
return;
ListNode scanner = head;
int length =0;
while(scanner != null){
length++;
scanner = scanner.next;
}
reorderHelper(head, length);
}
// helper returns the very last node's next node
public ListNode reorderHelper(ListNode start, int range){
if(range ==0)
return null;
ListNode result = null;
// range == 1 and range ==2 cases don't need adjustment
if(range ==1){
result = new ListNode(0);
result.next = start.next;
start.next = null;
return result;
}
if(range ==2){
result = new ListNode(0);
result.next = start.next.next;
start.next.next = null;
return result;
}
ListNode temp = reorderHelper(start.next, range -2);
result = new ListNode(0);
result.next = temp.next.next;
temp.next.next = start.next;
start.next = temp.next;
return result;
}
}
中有O（n）的操作 这样n次递归导致总体O（n平方）
如果坚持递归方法 需要返回调整好的list的尾节点的下一个节点 这个是从网友那里学
来的 其实这个过程有点tricky 为什么不简单返回 list的头节点或者尾节点 而要返
回尾节点的下一个节点呢？ 思路是这样的 尾节点经过调整已经不是原来的尾节点了
它指向的下一个已经不是原来的顺序 那为什么不返回头节点呢 ？ 头节点其实不需要
返回 每次用next找就可以了 而且每次拿到头节点也不好用 必须多次next找到尾节点
又超时了
网友的方法 我改编成了java的 后边也有返回尾节点的方法
但是很容易出错 如果面试 还是用循环而不是递归的方法 当然面试无法检查是不是超
时 所以用我最早的方法也可以吧
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if(head == null)
return;
ListNode scanner = head;
int length =0;
while(scanner != null){
length++;
scanner = scanner.next;
}
reorderHelper(head, length);
}
// helper returns the very last node's next node
public ListNode reorderHelper(ListNode start, int range){
if(range ==0)
return null;
ListNode result = null;
// range == 1 and range ==2 cases don't need adjustment
if(range ==1){
result = start.next;
start.next = null;
return result;
}
if(range ==2){
result = start.next.next;
start.next.next = null;
return result;
}
ListNode temp = reorderHelper(start.next, range -2);
result = temp.next;
temp.next = start.next;
start.next = temp;
return result;
}
}
但是我想如果一定要返回尾节点如何 我也找到了答案 但是返回值仅仅用于存储其下一
个节点
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if(head == null)
return;
ListNode scanner = head;
int length =0;
while(scanner != null){
length++;
scanner = scanner.next;
}
reorderHelper(head, length);
}
// helper returns the very last node's next node
public ListNode reorderHelper(ListNode start, int range){
if(range ==0)
return null;
ListNode result = null;
// range == 1 and range ==2 cases don't need adjustment
if(range ==1){
result = new ListNode(0);
result.next = start.next;
start.next = null;
return result;
}
if(range ==2){
result = new ListNode(0);
result.next = start.next.next;
start.next.next = null;
return result;
}
ListNode temp = reorderHelper(start.next, range -2);
result = new ListNode(0);
result.next = temp.next.next;
temp.next.next = start.next;
start.next = temp.next;
return result;
}
}
