a**********0
发帖数: 422 | 1 不递归无非就是分成两半 后一办reverse 然后插入到第一份去 我懒得写这么多代码
于是用了递归方法 结果超时 在自己电脑上跑了几个小case 都过了 不知道大家什么看
法 又超时了！
/**
* 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;
if(head.next ==null)
return;
if(head.next.next == null)
return;
ListNode scanner = head;
int length =0;
while(scanner != null){
length++;
scanner = scanner.next;
}
head = reorderHelper(head, length);
}
public ListNode reorderHelper(ListNode start, int range){
ListNode scanner =start;
ListNode last = start;
int count = range-2;
if(range ==0)
return null;
if(range ==1)
return start;
while(count >0){
count--;
scanner = scanner.next;
}
last = scanner.next;
scanner.next = null;
ListNode temp = reorderHelper(start.next, range -2);
start.next = last;
last.next = temp;
return start;
}
} | p*****e
发帖数: 537 | 2 我的没超时，供你参考。
// return the tail of the list (index = end+1)
ListNode* reorderHelper(ListNode* head, int start, int end){
if (start > end){
return NULL;
}
if (start == end) {
ListNode* tail = head->next;
head->next = NULL;
return tail;
}
else if (end == start + 1){
ListNode* tail = head->next->next;
head->next->next = NULL;
return tail;
}
ListNode* tail = reorderHelper(head->next, start+1, end-1);
ListNode* rt = tail->next;
tail->next = head->next;
head->next = tail;
return rt;
}
void reorderList(ListNode *head) {
if (!head) return;
int count = 0;
ListNode* n = head;
while(n){
count ++;
n = n->next;
}
reorderHelper(head, 0, count-1);
} | a**********0
发帖数: 422 | 3 雪中送炭啊
【在 p*****e 的大作中提到】
: 我的没超时，供你参考。
: // return the tail of the list (index = end+1)
: ListNode* reorderHelper(ListNode* head, int start, int end){
: if (start > end){
: return NULL;
: }
: if (start == end) {
: ListNode* tail = head->next;
: head->next = NULL;
: return tail;
| p*****e
发帖数: 537 | 4 那就发个包子给我呗，我如今是赤贫啊，想求个bless都没包子发 T_T | a**********0
发帖数: 422 | 5 没看懂
【在 p*****e 的大作中提到】
: 我的没超时，供你参考。
: // return the tail of the list (index = end+1)
: ListNode* reorderHelper(ListNode* head, int start, int end){
: if (start > end){
: return NULL;
: }
: if (start == end) {
: ListNode* tail = head->next;
: head->next = NULL;
: return tail;
| a**********0
发帖数: 422 | 6 原因找到了 递归method之中有一个线性的操作 这样会导致整体的n平方复杂度 | p*****e
发帖数: 537 | 7 其实和你的方法差不多啊，你用一个length，我用一个start index和end index。
比如：
0 -> 1 -> 2 -> 3 -> 4 -> 5,
helper(start=0, end=5) calls helper(start=1, end=4). helper(start=1, end=4)
把 1->2->3->4 reverse成 4->3->2->1,还返回5，那么helper(start=0, end=5)就把
header（0）和返回的那个5link起来，再link helper(start=1, end=4)的header就行
了。
【在 a**********0 的大作中提到】
: 没看懂
| a**********0
发帖数: 422 | 8 你的递归中没有O（n）的操作 我的有 所以用 length不好 应该直接给出最后一个节点
的指针
【在 p*****e 的大作中提到】
: 其实和你的方法差不多啊，你用一个length，我用一个start index和end index。
: 比如：
: 0 -> 1 -> 2 -> 3 -> 4 -> 5,
: helper(start=0, end=5) calls helper(start=1, end=4). helper(start=1, end=4)
: 把 1->2->3->4 reverse成 4->3->2->1,还返回5，那么helper(start=0, end=5)就把
: header（0）和返回的那个5link起来，再link helper(start=1, end=4)的header就行
: 了。
| a**********0
发帖数: 422 | 9 我觉得有个很难理解的
return的是本次调整之后链表的最后一个的下一个节点 并且此节点和前边部分不再链接
【在 p*****e 的大作中提到】
: 其实和你的方法差不多啊，你用一个length，我用一个start index和end index。
: 比如：
: 0 -> 1 -> 2 -> 3 -> 4 -> 5,
: helper(start=0, end=5) calls helper(start=1, end=4). helper(start=1, end=4)
: 把 1->2->3->4 reverse成 4->3->2->1,还返回5，那么helper(start=0, end=5)就把
: header（0）和返回的那个5link起来，再link helper(start=1, end=4)的header就行
: 了。
|
|
