已知一个单链表,设计一个复制单链表的算法
时间: 2023-03-16 21:45:05 浏览: 148
复制单链表的算法可以分为以下几个步骤:
1. 遍历原链表,创建一个新的链表,同时复制原链表中每个节点的值到新链表中对应的节点中。
2. 再次遍历原链表,将每个节点的 next 指针指向新链表中对应的节点。
3. 返回新链表的头节点。
具体实现可以参考以下代码:
```
struct ListNode* copyList(struct ListNode* head) {
if (head == NULL) {
return NULL;
}
// 创建新链表的头节点
struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
newHead->val = head->val;
newHead->next = NULL;
// 遍历原链表,复制节点到新链表中
struct ListNode* p = head->next;
struct ListNode* q = newHead;
while (p != NULL) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = p->val;
newNode->next = NULL;
q->next = newNode;
q = q->next;
p = p->next;
}
// 再次遍历原链表,将每个节点的 next 指针指向新链表中对应的节点
p = head;
q = newHead;
while (p != NULL) {
if (p->next != NULL) {
q->next->next = q->next;
}
p = p->next;
q = q->next;
}
return newHead;
}
```