好看的手机网站推荐,wordpress子目录伪静态,广州冼村旧改最新消息,网站名是什么目录 一、相交链表二、环形链表1三、环形链表2四、链表分割五、复制带随机指针的链表 一、相交链表
题目#xff1a; 示例#xff1a; 注意#xff1a;不能根据节点的值来比较是否相交#xff0c;而是根据节点在内存中是否指向相同的位置。
例如以上图#xff1a; 链表… 目录 一、相交链表二、环形链表1三、环形链表2四、链表分割五、复制带随机指针的链表 一、相交链表
题目 示例 注意不能根据节点的值来比较是否相交而是根据节点在内存中是否指向相同的位置。
例如以上图 链表A4、1、8、4、5 链表B5、6、1、8、4、5 链表A和链表B都有节点的值为1但是它们在内存中指向不同的位置而值为8的节点A的第三个节点、B的第四个节点则在内存中指向相同的位置。
大体思路链表A和链表B如果相交那么它们的后几个或者一个节点的位置是一样的。它们的长度不一定一样长所以要先计算出链表A和链表B的长度让较长的链表先走长度差的距离然后再同时走直到两个链表相交返回那个开始相交的节点。
计算链表长度 分别定义一个变量遍历链表不为空计数器加1往后走直到循环结束跳出。
如果没有相交返回空 此时分别遍历两个链表的指针已经走到尾了。假设两个链表有相交不管是一个还是多个那么这两个指针肯定是一样的指相交如果两个链表不相交即使是最后的节点也同样不相交所以就直接返回NULL。
较长的链表先走节点数之差 用一个变量等于链表长度之差因为并不知道是A链表长还是B链表长所以使用绝对值函数abs。先假设是A链表长B链表短。设置一个条件如果A链表的长度小于B链表的长度就反过来。如果假设的是对的较长的链表先走长度之差的距离。
一起走直到相交 两个链表同时走到某个节点相交了就跳出循环然后赋给新的头指针并且返回这个头指针。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int len10;int len20;struct ListNode *cur1headA;struct ListNode *cur2headB;//先算出两个链表的节点数while(cur1){len1;cur1cur1-next;}while(cur2){len2;cur2cur2-next;}//如果没有相加点返回空if(cur1!cur2){return NULL;}//长的先走节点数之差int kabs(len1-len2);struct ListNode *longheadheadA;struct ListNode *shortheadheadB;if(len1len2){longheadheadB;shortheadheadA;}while(k){longheadlonghead-next;k--;}//一起走直到相交while(longhead!shorthead){longheadlonghead-next;shortheadshorthead-next;}struct ListNode *newheadlonghead;return newhead;
}二、环形链表1
题目 使用的是双指针法
定义两个快慢指针fast和slow从起点出发。先fast一次走两步slow一次走一步再判断两个指针是否相同。如果链表有环那么fast或者fast-next永远不为空一直在循环里转如果链表没有环fast又走得比slow快所以fast或者fast-next到空就结束。这里fast比slow快一步即每次距离缩短1步所以只要有环fast先在环里转然后slow随后进环每次它们的距离缩短1最终相遇。
bool hasCycle(struct ListNode *head) {struct ListNode *slowhead;struct ListNode *fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){return true;}}return false;
}三、环形链表2
题目 这题与上面的题多增加了一个设定如果有环返回的是开始入环的第一个节点。没有环返回空。
那么始入环的第一个节点怎么找呢其实这里是有关数学计算的。
还是使用两个快慢指针fast一次走两步slow一次走一步。如果链表没有环fast或者fast-next为空然后返回空指针。如果链表有环在环的某个位置相遇注意fast先入环可能已经在环里转了n圈了。假设相遇点与入环点的距离为x起始点到入环点的距离为L环的剩下的距离为nC-xn表示fast已经在环里转了n圈。
fast从起始点到相遇点的距离为LnCx slow从起始点到相遇点的距离为Lx
因为fast一次的步长为slow的两倍 所以 2LxLnCx LxnC LnC-x 根据数学计算转换为两个指针分别一个从相遇点走另一个从起始点走以相同的步长它们会在入环的第一个节点相遇然后返回这个相遇点就是入环的第一个节点。 struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slowhead;struct ListNode *fasthead;while(fastfast-next){fastfast-next-next;slowslow-next;if(slowfast){struct ListNode *ridslow;struct ListNode *mridhead;while(rid!mrid){ridrid-next;mridmrid-next;}return rid;}}return NULL;
}四、链表分割
题目 假设一个链表为 2、3、1、4、2、5 假设x等于3数据小于的3的节点有2、1、2 大于等于3的节点有3、4、5
题目要求将小于x的节点排在其余节点之前并且不能改变原来的数据顺序。
大体思路这里我们可以采用分为两个链表的方式。将数据小于x的节点放在一个A链表里大于等于的放在B链表里。然后把A链表的尾节点与B链表的头节点连接起来。
但是这里要注意一个问题如果A链表没有节点怎么与B链表连接这种情况要单独判断比较麻烦。所以我们可以采用创建哨兵位头节点解决这个问题。
注意最后B链表的尾节点要指向空指针同时释放两个哨兵位节点返回第一个有效节点。
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* curpHead;struct ListNode* head1, *tail1, *head2, *tail2;head1tail1(struct ListNode*)malloc(sizeof(struct ListNode));head2tail2(struct ListNode*)malloc(sizeof(struct ListNode));while(cur){if(cur-valx){tail1-nextcur;tail1tail1-next;}else{tail2-nextcur;tail2tail2-next;}curcur-next;}tail2-nextNULL;tail1-nexthead2-next;struct ListNode* newheadhead1-next;free(head1);free(head2);return newhead;}
};五、复制带随机指针的链表
题目 要拷贝原节点并且拷贝节点的随机指针也要指向对应的节点最后还原原链表。
每个拷贝节点都在原节点的后面 用一个变量cur遍历链表只要不为空每次进入循环先定义一个变量next记录原链表的下一个位置cur在原链表的下一个位置方便一次拷贝完找到然后开辟一块空间copy为拷贝节点把原节点的值赋给拷贝节点再让cur的下一个地址为copycopy连接next。 置每个拷贝random 原链表的每个节点的random指针都有对应的指向拷贝节点也要有random指针对应的指向只是拷贝节点的random指针要与原节点的random指针指向保持一致。比如原节点13的random指针指向原节点的7那么拷贝节点13的random指针则指向拷贝节点的7。
问题是拷贝节点的random指针怎么找到它对应的节点呢其实上面一步把每个拷贝节点放在原节点的后面有一个好处方便这一步找到它的random指针。
以拷贝节点13为例拷贝节点13的random指针就是它的原节点的random指针所指向的原节点的下一个节点。如果原节点的random指向空拷贝节点的randon也是指向空。 拷贝节点解下来尾插在一起恢复原链表
struct Node* copyRandomList(struct Node* head) {struct Node* curhead;//复制某个节点到原节点的后面while(cur){struct Node* nextcur-next;struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;cur-nextcopy;copy-nextnext;curnext;}curhead;//处理拷贝节点的random指针指向while(cur){struct Node* copycur-next;if(cur-randomNULL){copy-randomNULL;}else{copy-randomcur-random-next;}curcopy-next;}curhead;//把拷贝指针连接起来还原原来的链表struct Node* newheadNULL;struct Node* tailNULL;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;if(tailNULL){newheadtailcopy;}else{tail-nextcopy;tailtail-next;}cur-nextnext;curnext;}return newhead;
}感谢观看~
