邢台网站建设03191688,夺目视频制作网站,网站流,北京模板网站建设公司目录
一. 相交链表
二. 环形链表
三. 环形链表之寻找环形入口点
四. 判断链表是否是回文结构
五. 随机链表的复制 一. 相交链表 最简单粗暴的思路#xff0c;遍历两个链表#xff0c;分别寻找是否有相同的对应的结点。 我们对两个链表的每个对应的节点进行判断比较…目录
一. 相交链表
二. 环形链表
三. 环形链表之寻找环形入口点
四. 判断链表是否是回文结构
五. 随机链表的复制 一. 相交链表 最简单粗暴的思路遍历两个链表分别寻找是否有相同的对应的结点。 我们对两个链表的每个对应的节点进行判断比较如果不相等的话 那么我们就进行换下一对节点进行判断
但这里存在一个弊端两条链表可能有一条长一条短存在节点数不一样的情况挨个比较。 举例来说只是举例来说 假设一个链表是6个节点一个是8个节点那么差值就是8 那么我们让长的那个链表优先走 | 8-6 | 步走后两个链表长度一致就能开始进行比较了 解决这个问题很简单-- 遍历计算两个链表长度求差让长的先走完差值步使两条链表长度一致。 于是思路有步骤有√
求差求两个链表长度差值让长的链表先走差值步 遍历两个链表分别对应是否指向相同的结点
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//1. 遍历两个链表求他们的长度差//设置两个链表头结点方便遍历ListNode* l1 headA;ListNode* l2 headB;//设置变量存放链表长度方便求差int sizeA0,sizeB0;//遍历计算两条链表长度ingwhile(l1){sizeA;l1 l1-next;}while(l2){sizeB;l2 l2-next;}//求长度差int gap abs(sizeA-sizeB);//abs 绝对值函数//2.长链表先走长度差步//由于不知道哪个链表长先随便定义再判断ListNode* longList headB;ListNode* shortList headA;if(sizeA sizeB){longList headA;shortList headB;}//长链表先走while(gap--){longList longList-next;}//此时的longList和shortList在同一起跑线//3. 遍历两个链表要么相交要么不相交while(longList shortList)//条件是两个链表都不得是空{if(longList shortList)//找到相同结点相交{return longList;//反正相同结点返回long 和short 都一样}//不相同换下一结点继续比较longList longList-next;shortList shortList-next;}return NULL;//循环结束可见不相交返回空}
二. 环形链表 类似追击问题若快指针在追慢指针的时候追到了说明链表带环 如果链表不是带环的那么快慢指针是绝对不会相遇的 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {//创建快慢指针ListNode* slow head;ListNode* fast head;while(fast fast-next){//慢指针走一步快指针走两步相当于快在一步一步追慢slow slow -next;fast fast -next-next;//相遇说明带环if(fast slow){return true;}}return false;
}
三. 环形链表之寻找环形入口点 假设meet为快慢指针相遇点 遍历头结点pcur和meet,因为环形终将相遇 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {//1. 找快慢指针相遇点-说明是环形结点ListNode* slow head;ListNode* fast head;while(fast fast -next){slow slow -next;fast fast -next-next;if(fast slow)//找到相遇点是环形{//2. 遍历头结点和快慢指针相遇点每次一步其相遇点就是环形入环第一个结点ListNode* pcur head; //定义头结点while(pcur ! fast){//但凡是环形肯定会相遇pcur pcur -next;fast fast -next;}return pcur;}}return NULL;
}
四. 判断链表是否是回文结构 先找中间结点快慢指针 再将中间结点之后的链表反转最后链表左右进行比较看是否相同 /*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {//1. 找中间结点ListNode* slow A;ListNode* fast A;while(fast fast-next){slow slow-next;fast fast-next-next;}ListNode* mid slow;//2. 根据中间结点反转后面的链表ListNode* n1 NULL;//指向空ListNode* n2 mid;//指向中间结点ListNode* n3 n2-next;//指向n2的下一个结点while(n2){n2-next n1;//n2指向其前一个结点初始是空n1 n2;//n1往后走n2 n3;//n2往后走if(n3)//前提n3不得为空n3才能继续往后走n3 n3-next;//n3往后走}ListNode* right n1;//n1为我反转链表的头结点//3. 比较原链表和反转链表的结点ListNode* left A;//原链表头结点while(right)//反转链表的尾结点是指向空的当其走到空说明遍历完了{if(left-val ! right-val){//有不相等的值说明不回文return false;}left left-next;right right-next;}return true;}
};
五. 随机链表的复制 思路 原链表上复制并插入复制结点 赋值random 断开链表 /*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/
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* pcur head;//头结点while(pcur){Node* Next pcur-next;//原链表的下一结点Node* newnode buynode(pcur-val);//要复制的新结点newnode-next Next;pcur-next newnode;pcur Next;//pcur走到下一结点}}struct Node* copyRandomList(struct Node* head) {if(head NULL){return NULL;}//1. 原链表上复制结点//此时链表是 node1 - newcopy1 - node2 - newcopy2- node3..AddNode(head);//2. 赋值randomNode* pcur head;while(pcur){//循环修改random指针Node* copy pcur-next;//此时pcur的下一结点即上一步插入的复制结点if(pcur-random ! NULL){//因为创建新的节点时直接让random指向空现在只需将原链表中random不指向空的进行处理copy-random pcur-random-next;}pcur copy-next;//copy下一结点为原链表的下一结点}//3. 断开链表pcur head;//让pcur回到头结点Node* newhead,*newtail;//为新链表创建头结点和要遍历连接的结点newhead newtail pcur-next;//pcur下一结点就是复制的新链表的头结点while(pcur-next-next)//因为有多插入复制的所以pcur-next-next才是原链表下一结点{pcur pcur-next-next;//pcur走到原链表下一结点newtail-next pcur-next;//新链表连接新链表被复制的下一结点newtail newtail-next;//新链表往后走}return newhead;//返回新链表头结点
} 希望对你有帮助
