问题
已知一个简单链表，请复制链表并返回头结点指针。
解法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;
}
}