AC is a lifestyle

那天马师兄说今年人民搜索最后一道笔试题没多少人写出非常好的方法：一个单链表除了next指针外，还带有一个随机指针（设为rand）指向任意元素，用最少的时间复杂度和最少的空间复制该链表。

稍微讨论了一下，可以用O(n)的时间复杂度和O(1)的附加空间实现：根据源链表依次复制出新链表的对应节点，并将新节点插入到源节点后，新链表的rand指针指向原链表的rand；然后遍历一遍链表，将新链表的rand指针指向对应元素的next元素（即新链表中对应的rand指针元素）；最后将新链表和源链表分离。

代码如下：

/*
 * Author: Lixiang Liu @ ICT, CAS
 * File Name: goso_list_copy.c
 * TODO:用C++类实现
 */
#include <stdio.h>
#include <stdlib.h>

struct node_t {
    int data;
    struct node_t *next;
    struct node_t *rand;
};

struct node_t * copylist(struct node_t **dest, struct node_t *src) {
    struct node_t *p, *q;
    p = src;
    while (p != NULL) {
        q = (struct node_t *)malloc(sizeof(struct node_t));
        q->data = p->data;/*XXX: copy p->data to q->data*/
        q->next = p->next, q->rand = p->rand;
        p->next = q;
        p = q->next;
    }
    p = src;
    while (p != NULL) {
        q = p->next;
        q->rand = q->rand->next;
        p = q->next;
    }
    p = src;
    *dest = p->next;
    while (p != NULL) {
        q = p->next;
        p->next = q->next;
        p = p->next;
        if (p != NULL) q->next = p->next;
    }
    return *dest;
}

int main(int argc, char *argv[]) {
    /*test code*/
    struct node_t *src, *dest, *p, *q;
    int i = 0;
    src = NULL;
    for (i = 0; i < 10; i++) {
        p = (struct node_t *)malloc(sizeof(struct node_t));
        p->data = 10-i;
        p->next = p->rand = src;
        src = p;
    }
    p = src;
    for (i = 0; i < 10; i++) {
        int j, s = ((i+1)*7) % 10;
        q = src;
        for (j = 0; j < s; j++) {
            q = q->next;
        }
        if (q == NULL) q = src;
        p->rand = q;
        p = p->next;
    }
    printf("------source list:\n");
    p = src;
    for (i = 0; i < 10; i++) {
        printf("%d\t%d \t%d\n", p, p->data, p->rand->data);
        p = p->next;
    }
    copylist(&dest, src);
    printf("====compare with destination list:\n");
    p = src, q = dest;
    for (i = 0; i < 10; i++) {
        printf("%d:%d\t%d -- %d\t\t%d -- %d\n", p, q, p->data, q->data, p->rand->data, q->rand->data);
        p = p->next;
        q = q->next;
    }
    /*free memory space*/
    p = src, q = dest;
    for (i = 0; i < 10; i++) {
        p = p->next;
        q = q->next;
        free(src);
        free(dest);
        src = p;
        dest = q;
    }
    return 0;
}

各种笔试面试有各种关于链表的题（复制、找环、反转等等），这种题考实现还好，用来考“算法”其实没啥意思（毕竟很多人用应试的方法来准备这种题）。

今天yahoo的研究类题目非常刺激啊（网上题目URL待补，看来博士要通过雅虎的笔试题很难啊），其中第三题问如何用O(1)空间判断一个单向链表（的元素）是否对称，还算有意思。

数据结构：

struct Node {
    char data;
    Node *next;
};

个人yy了一个O(n)时间复杂度的解法：先把单向链表的后一半反向，然后前后进行对比看是否相等，判断完后将单向链表恢复原样。

其他不多说，直接上代码（未测试）：

bool isParalindom(Node *head)
{
    bool res = true;
    int len = 0;
    Node *p = head, *q, *r, *s;
    while (p != NULL) p = p->next, len++; //求长度
    q = head;
    for (int i = (len+1) / 2; i >= 0; i--) q = q->next; //定位到链表的后一半（若为奇数个元素则跳过最中间元素）
    r = NULL;
    while (q != NULL) { //翻转链表的后一半
        p = q->next; q->next = r;
        r = q; q = p;
    }
    q = r;
    p = head;  res = true;
    while (r != NULL) {//判断前后是否对称
        if (r->data != p->data) {
            res = false;
            break;
        }
        p = p->next, r = r->next;
    }

    while (p->next != NULL) p = p->next;
    r = NULL;
    while (q != NULL) {//将后面一半翻转回链表的原样
        s = q->next; q->next = r;
        r = q; q = s;
    }
    p->next = r;
    return res;
}