数据结构：单链表的应用（力扣算法题）第三章

代码汇总：登录 - Gitee.com

前两章回顾：

​​​​​​数据结构：单链表的应用（力扣算法题）第一章-CSDN博客

数据结构：单链表的应用（力扣算法题）第二章-CSDN博客

1.链表分割

链表分割_牛客题霸_牛客网

理解题意：

思路：

创建两个链表（小链表，大链表），遍历原链表，小的尾插到小链表中，大的尾插到大链表中，再将小链表和大链表相连。

代码如下：

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {//定义两链表ListNode* lessHead, *lessTail;lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));ListNode* greaterHead, *greaterTail;greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//遍历ListNode* curr = pHead;while(curr){//尾插到小链表if(curr->val < x){lessTail->next = curr;lessTail = lessTail->next;}else{//尾插到大链表greaterTail->next = curr;greaterTail = greaterTail->next;}curr = curr->next;}//大链表尾结点置空greaterTail->next = NULL;//相连lessTail->next = greaterHead->next;ListNode* ret = lessHead->next;free(lessHead);free(greaterHead);return ret;}
};

最终通过测试。

2.随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

理解题意：

浅拷贝：对值的拷贝，如形参和实参。

深拷贝：重新生成一个新的地址，并保存相同的值。

满足题意的最终结果：

其中copyphead为复制后的链表，最终返回copyphead。

思路：

第一步：

定义一个指针curr，以此遍历phead链表，并且在遍历过程中，只要当前结点不为空，依次保存当前的结点到新链表copyHead。

新的结点均通过尾插连接。

但是对于杂乱无章的random指针，我们应该怎么做？

对于random指针，我们可以将所有指针都置为空，再依次遍历，首先，创建copycurr指针，将random指针依次遍历，但是对于随机的，向后或向前指向的指针，不太好改变，所以此种方法暂时放弃。

第二步：

（1）在原链表基础上拷贝结点

通过curr遍历，每遍历一个结点，都新申请一个结点的空间newnode并且新建立一个结点，将其尾插到原本的结点之后，使其完成 newnode -> next = curr -> next; curr -> next = newnode;再使curr指针指向原本链表的下一个结点……以此类推。

(2）放置random指针

此时，是将复制好的链表都插入到了原链表之间，通过copy -> random = curr -> random ->next;将其curr与copy相关联。

（3）断开新旧链表

使新链表的next指针指向它自己的结点，同时可以选择，（可选）使旧链表也指向自己的下一结点。

代码如下：

此时，这里有错：

发现我们缺少对空链表的解决。

typedef struct Node Node;
//申请结点
Node* buyNode(int x)
{Node* newnode = (Node*)malloc(sizeof(Node));newnode->val = x;newnode->next = newnode->random = NULL;return newnode;
}
//增加结点
void AddNode(Node* head)
{Node* curr = head;while(curr){//创建一样的结点Node* newnode = buyNode(curr->val);Node* next = curr->next;//此处next用于保存原链表下一结点//插入  newnode->next = next;curr->next = newnode;curr = next;}
}
//放置random
void setRandom(Node* head)
{Node* curr = head;while(curr){Node* copy = curr->next;if(curr->random)copy -> random = curr -> random ->next;curr = copy->next;}
}struct Node* copyRandomList(struct Node* head) {if(head == NULL){return head;}//(1)AddNode(head);//(2)setRandom(head);//(3)Node* curr = head;Node* copyHead,*copyTail;copyHead = copyTail = curr->next;while(copyTail->next){curr = copyTail->next;copyTail->next = curr->next;copyTail = copyTail->next;}return copyHead;
}

最终通过测试。

本章完。