c*****a
发帖数: 808 | 1 是不是shuffle打乱链表啊
copy a linked list where the data member of each node in the linked list
could be any other node in the linked list. |
l*****a
发帖数: 14598 | 2 linked list有一个指针data member,可能指向这个连表中任意结点
【在 c*****a 的大作中提到】
: 是不是shuffle打乱链表啊
: copy a linked list where the data member of each node in the linked list
: could be any other node in the linked list.
|
j*****y
发帖数: 1071 | 3 struct Node
{
Node * next;
Node * node;
}
copy this linked list
【在 c*****a 的大作中提到】
: 是不是shuffle打乱链表啊
: copy a linked list where the data member of each node in the linked list
: could be any other node in the linked list.
|
M********5
发帖数: 715 | 4 写了个c++版本的，O(n)的time efficiency和O(n)的space efficiency，不知道有没有
更优化的？比如no extra space and only one time walk-through?
struct Node{
Node* data;
Node* next;
};
Node* copyLinkedList(Node* head){
if(!head)
return NULL;
std::map node_map;
Node* new_head = copyLinkedListHelper(head, node_map);
Node* cur = new_head;
while(head){
cur->node = node_map[head->node];
cur = cur->next;
head = head->next;
}
return new_head;
}
Node* copyLinkedListHelper(Node* head, std::map& n_map){
if(!head)
return NULL;
Node* n = new Node;
n_map[head] = n;
n->next = copyLinkedListHelper(head->next, n_map);
return n;
} |
c*****a
发帖数: 808 | 5 写出来了
public static ListNode copyLink(ListNode node){
ListNode original = node, head = null, newOne=null,next;
//insert node inbetween, so abc becomes aabbcc
while(original!=null){
newOne = new ListNode(original.val);
next = original.next;
original.next = newOne;
newOne.next =next;
original = next;
}
//new list
head = node.next;
//copying random link
original = node;
while(original!=null){
original.next.datamember = original.datamember.next;
original = original.next.next;
}
//separte two lists out
original = node;
newOne = original.next;
while(original!=null && newOne!=null){
next = newOne.next;
if(next!=null){
original.next= next;
newOne.next = next.next;
newOne = newOne.next;
}
original = next;
}
return head;
} |
M********5
发帖数: 715 | 6 这个idea很好，duplicate linked list，估计我要是在phone interview的时候这么写
肯定会出bug，但是这在space上应该是很优化的
【在 c*****a 的大作中提到】
: 写出来了
: public static ListNode copyLink(ListNode node){
: ListNode original = node, head = null, newOne=null,next;
: //insert node inbetween, so abc becomes aabbcc
: while(original!=null){
: newOne = new ListNode(original.val);
: next = original.next;
: original.next = newOne;
: newOne.next =next;
: original = next;
|
y********9
发帖数: 130 | 7 这道题貌似超有名 前段时间有人发过 没看过答案写最优解我觉得很难啊 |
M********5
发帖数: 715 | 8 最优解是不是就是lz发的这个？如果是的我觉得这个要当场写的bugfree确实不容易。
。。
【在 y********9 的大作中提到】
: 这道题貌似超有名 前段时间有人发过 没看过答案写最优解我觉得很难啊
|
H****s
发帖数: 247 | 9 对！这个就是标准答案。
【在 M********5 的大作中提到】
: 最优解是不是就是lz发的这个？如果是的我觉得这个要当场写的bugfree确实不容易。
: 。。
|
j******2
发帖数: 362 | 10 哪家的店面问过啊？
【在 M********5 的大作中提到】
: 这个idea很好，duplicate linked list，估计我要是在phone interview的时候这么写
: 肯定会出bug，但是这在space上应该是很优化的
|
c********t
发帖数: 5706 | 11 赞，问一下，最后一次拆分循环
条件 while(original!=null && newOne!=null)， 可不可以改为while(original!=
null）什么情况original不是null, newOne为null?
【在 c*****a 的大作中提到】
: 写出来了
: public static ListNode copyLink(ListNode node){
: ListNode original = node, head = null, newOne=null,next;
: //insert node inbetween, so abc becomes aabbcc
: while(original!=null){
: newOne = new ListNode(original.val);
: next = original.next;
: original.next = newOne;
: newOne.next =next;
: original = next;
|
