链表复制算法

问题

已知一个简单链表，请复制链表并返回头结点指针。

解法1：遍历算法

从头开始遍历原链表，依次复制链表各个节点。

结点定义如下：

struct node {
    int data;
    struct node* next;
};
typedef struct node* pNode;

创建新结点newNode代码：

pNode newNode(int data){
    pNode nd = (pNode)malloc(sizeof(node));
    nd->data = data;
    nd->next = NULL;
    return nd;
}

复制链表函数，注意第一个结点的特殊情况。此外保留有尾结点指针，便于新结点插入到链表中。

struct node* copyList(struct node* head) {
    struct node* current = head;
    struct node* newList = NULL; //新链表的头指针
    struct node* tail = NULL; // 新链表的尾部指针
    while (current != NULL) {
        if (newList == NULL) { // 特殊情况，第一个新结点
            newList = newNode(current->data);
            tail = newList;
        }
        else {
            tail->next = newNode(current->data);
            tail = tail->next;
        }
        current = current->next;
    }
    return(newList);
}

如果要把第一个新结点这种特殊情况一起考虑，则可以使用指向指针的指针来实现。代码如下：

void push(struct node** headRef, int data)
{
    pNode nd = newNode(data);
    nd->next = *headRef;
    *headRef = nd;
}
struct node* copyListWithRef(struct node* head)
{
    struct node* current = head;
    struct node* newList = NULL;
    struct node** lastPtr = &newList;

    while (current != NULL) {
        push(lastPtr, current->data);  
        lastPtr = &((*lastPtr)->next);
        current = current->next;
    }
    return newList;
}

解法2：递归算法

使用递归使得代码量很少，逻辑也很清晰。主要思路是首先复制原链表头结点，递归调用函数复制链表的剩下部分，并设置新链表头结点的next域指向复制的剩下部分链表。代码如下：

pNode copyListRecursive(pNode head)
{
    if (head == NULL) return NULL;
    else {
        pNode newList = newNode(head->data);  //复制原链表头结点，新链表头部指向它
        newList->next = copyListRecursive(head->next); //新链表的next指向复制的剩下链表部分
        return newList;
    }
}