一道超难的算法题-复制链表
Rui在参加面试后，给我分享了一道算法题。他在留言中说made me wanna kill myself when I knew the answer.
题目如下：
Given a Linked List of node structure asstruct Node { type element; Node *next; Node *arb;};You are asked to create an exact copy this linked list. Pointer arb points to an arbitrary node in the linked list.
先说说我的算法吧。我选择了一个超笨的方法完成：创建一个新的linked list存储原始链表每个节点的顺序号，然后复制链表的时候，通过顺序号，找到arb指针所指向的节点。算法很笨，无论是空间效率还是时间效率，都很差。不过好歹是完成了。
不过，在我看完答案之后，我也wanna kill myslef。太神奇了。
算法首先在每两个节点之间插入一个新的节点。然后循环每组节点：
- p->next->arb = p->arb->next;
- p = p->next->next;
我顺手写了段实现代码，没编译，没调试，没测试。
- typedef struct {
- int data; // assuming data is an integer
- Node *next;
- Node *arb;
- }Node;
- void copy_linked_list(Node * src, Node ** dst) {
- Node *p;
- Node *q = NULL;
- for (p = src; p; p=p->next->next) {
- // Initialize the new node
- Note *nn = (Node *)malloc(sizeof(Node));
- nn->data = p->data;
- nn->arb = NULL;
- // Add the node to the right of the src node
- nn->next = p->next;
- p->next = nn;
- }
- // Create arb pointer
- for(p = src; p; p = p->next->next)
- p->next->arb = p->arb->next;
- // Detach copy node and create destination linked list
- for (p = src, q = *dst; p; p = p->next-next, q = q->next) {
- r = p->next;
- p->next = p->next-next;
- if (q->next)
- q->next = q->next->next;
- else
- q->next = NULL;
- if (q)
- q = r;
- else
- q->next = r;
- }
- }
其实Rui早在3月份就给我发了这道题目，我也早在几个月前，看到了正确答案。一直想把这道题作为面试题，可觉得太难了，不想难为candidate了。
