网站制作软件区别,网页设计尺寸一般是多少,两个wordpress文章同步,站长源码论坛目录 一、链表的回文结构
二、相交链表
三、环形链表
四、环形链表Ⅱ
五、复制带随机指针的链表 一、链表的回文结构 题目描述#xff1a;链表的回文结构_牛客题霸_牛客网 对于这道题#xff0c;如果没有前面的一些题的基础#xff0c;是非常难做的#xff0c;我们的思…目录 一、链表的回文结构
二、相交链表
三、环形链表
四、环形链表Ⅱ
五、复制带随机指针的链表 一、链表的回文结构 题目描述链表的回文结构_牛客题霸_牛客网 对于这道题如果没有前面的一些题的基础是非常难做的我们的思路是这样的先找到链表的中间结点然后从中间结点开始将后半段链表逆置然后依次比较即可。所以这里就需要复用前面题目的函数了代码如下所示 /*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:struct ListNode* middleNode(struct ListNode* phead){struct ListNode* fastphead;struct ListNode* slowphead;while(fastfast-next){fastfast-next-next;slowslow-next;}return slow;}struct ListNode* reverse(struct ListNode* phead){struct ListNode* prevNULL;struct ListNode* curphead;while(cur!NULL){struct ListNode* nextcur-next;cur-nextprev;prevcur;curnext;}return prev;}bool chkPalindrome(ListNode* A) {// write code herestruct ListNode* pheadA;struct ListNode* middlemiddleNode(phead);struct ListNode* NewHeadreverse(middle);struct ListNode* cur1phead;struct ListNode* cur2NewHead;while(cur2!NULL){if(cur1-valcur2-val){cur1cur1-next;cur2cur2-next;}else{return false;}}return true;}
}; 二、相交链表 题目链接力扣 对于这道题我们可以采用最简单的双层暴力循环做出来。但是那样效率太低我们其实可以先算出两个链表的长度然后让长的链表都差值步最后两个链表一块走如果遇到两个结点的地址相同那么就是相交的位置 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* cur1headA;struct ListNode* cur2headB;int len10;int len20;while(cur1){len1;cur1cur1-next;}while(cur2){len2;cur2cur2-next;}cur1headA;cur2headB;if(len1len2){int lenlen1-len2;while(len--){cur1cur1-next;}}else{int lenlen2-len1;while(len--){cur2cur2-next;}}while(cur1!cur2){cur1cur1-next;cur2cur2-next;}return cur1;
} 三、环形链表 题目链接力扣 对于这道题我们可以采用快慢指针法来完成试想一下让快指针走两步慢指针走一步那么当慢指针走到环的入口的时候快指针一定在环里面走了一段距离了而每次快指针与满指针的距离都会缩短一步。那么一定会追的上。最终代码如下所示 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* fasthead;struct ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){return true;}}return false;
} 然而我们在这里会思考一个问题慢指针走一步快指针走两步如果带环最后一定可以相遇吗如果快指针走三步四步呢 对于这个问题我们需要好好思考一下。我们假定下面这样一个带环的链表 当fast走进环入口的时候slow正好走到一半 当slow走到入口的时候fast已经在环内某个位置了我们不妨记作此时fast距离slowN步这样的话由于距离每次减少1。所以N最终一定会减到0。所以会相遇那么如果是fast一次三步呢 我们还是上图进行分析 对于现在相差N步由于每次距离减少2 所以当N为偶数的时候一定会减为0 当N为奇数的时候这时候fast就最终一定会超越slow一步此时进入新一轮的追击 我们设周长为C,那么fast需要追C-1步 这样的话当C-1为偶数的话自然追的上C-1为奇数的话则永远也不可能追的上 当fast为一次走四步的时候也是同理的。 在这里我们或许还会碰到一个新的问题如何计算环的长度这个思路其实也很简单我们只需要求出相遇点然后让一个指针不动另外一个指针一直走然后计数即可。当回到相遇点的时候正好就是环的长度 四、环形链表Ⅱ 题目链接力扣 对于这道题我们可能就比较难以思考了。 我们的分析过程是这样的 由于是环形链表那么我们可以求出他的相遇点既然有了相遇点。我们继续设相遇点与入口的距离为X头节点与入口点的距离为L 然后我们计算fast和slow两个指针在相遇的瞬间他们已经走的距离 fast的距离为LN*CX其中N大于等于1。因为fast先入环需要追击一圈 slow的距离为LX 注意这里slow在环内所走的路程一定不超过一圈即0XC这是因为fast的速度是slow的二倍假如fast追赶slow所需要的路程不超过C-1由于相对速度为1那么slow所走的路程就不超过C-1。 由于fast的速度是slow的二倍所以fast的路程是slow的二倍。 所以 LN*CX2(LX) 可以得出LN*C-X 为了方便理解可以进一步化简为L(N-1)*C-X 这个公式的物理意义就是一个指针从头结点开始走一个指针从相遇点走那么必然相遇于入口。代码为 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fasthead;struct ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){struct ListNode* meetfast;while(meet!head){meetmeet-next;headhead-next;}return meet;}}return NULL;
} 其实对于这道题还有另外一种思路我们可以将相遇点和相遇点的下一个结点断开然后让相遇点的下一个结点作为头结点这样就转化为了相交链表的问题 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* cur1headA;struct ListNode* cur2headB;int len10;int len20;while(cur1){len1;cur1cur1-next;}while(cur2){len2;cur2cur2-next;}cur1headA;cur2headB;if(len1len2){int lenlen1-len2;while(len--){cur1cur1-next;}}else{int lenlen2-len1;while(len--){cur2cur2-next;}}while(cur1!cur2){cur1cur1-next;cur2cur2-next;}return cur1;
}
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fasthead;struct ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){struct ListNode* meetfast;struct ListNode* list1meet-next;struct ListNode* list2head;meet-nextNULL;return getIntersectionNode(list1,list2);}}return NULL;
} 五、复制带随机指针的链表 题目链接力扣 解法一 对于这道题我们有一种比较简单的思路直接暴力求解。 具体思路是首先将普通的链表拷贝下来。先不处理random指针。这个比较简单 然后我们开始处理random对于random我们只能采用相对位置来进行记录。这样的话时间复杂度达到了O(N²) 我们直接给出代码 /*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* copyheadNULL;struct Node* copytailNULL;struct Node* curhead;while(cur){struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;copy-nextNULL;if(copyheadNULL){copyheadcopytailcopy;}else{copytail-nextcopy;copytailcopy;}curcur-next;}curhead;struct Node* copycurcopyhead;while(cur){if(cur-randomNULL){copycur-randomNULL;copycurcopycur-next;}else{struct Node* cur2head;int count0;while(cur2!cur-random){cur2cur2-next;count;}struct Node* copycur2copyhead;while(count--){copycur2copycur2-next;}copycur-randomcopycur2;copycurcopycur-next;}curcur-next;}return copyhead;
} 解法二 我们可以不难看出上面的时间复杂度太大了我们可以对上面的解法进行一点点的优化我们采用指针数组先将每个random的地址给记录下来最后在赋值这样也是可以的。但是仅仅只是优化了一点点。 解法三 想要真正的优化时间复杂度那么我们必须要从思路开始下手了。 我们可以采用这样的思路 首先这是我们的原来的链表 我们可以在每一个结点的后面拷贝一个结点出来如下图所示 最终形式如下图所示 对于这个操作其实是不难的 这部分的代码如下所示 复制完成以后我们接下来就要处理random了 最后一步就是解开原链表 。 解开原来的链表我们需要使用一个copyhead和copytail指针来管理copy链表并且逐步解开解开 最终代码如下所示 /*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {//复制struct Node* curhead; while(cur){struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;struct Node* nextcur-next;cur-nextcopy;copy-nextnext;curnext;}//处理randomcurhead;while(cur){struct Node* copycur-next;if(cur-randomNULL){copy-randomNULL;}else{copy-randomcur-random-next;}curcur-next-next;}//解开两个链表curhead;struct Node* copyheadNULL;struct Node* copytailNULL;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;if(copyheadNULL){copyheadcopytailcopy;cur-nextnext;}else{copytail-nextcopy;copytailcopy;cur-nextnext;}curnext;}return copyhead;
} 本节内容到此为止
如果对你有帮助的话不要忘记点赞加收藏哦
