如何搭建app开发平台,seo推广培训课程,商品详情页设计图,微信小程序客户管理系统一、环形链表
141.环形链表#xff08;题目链接#xff09; 思路#xff1a;使用快慢指针#xff0c;慢指针走一步#xff0c;快指针走俩步#xff0c;如果是环形链表#xff0c;那么快慢指针一定相遇#xff0c;如果不是环形结构那么快指针或者快指针的next一定先为N…一、环形链表
141.环形链表题目链接 思路使用快慢指针慢指针走一步快指针走俩步如果是环形链表那么快慢指针一定相遇如果不是环形结构那么快指针或者快指针的next一定先为NULL. 代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode ;
bool hasCycle(struct ListNode *head) {if(headNULL||head-nextNULL){return false;}ListNode* fasthead;ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){return true;}}return false;} 二、环形链表||
142.环形链表||题目链接 思路用快慢指针方式。慢指针走一步快指针走俩步如果是环形那么快慢指针第一次相遇快指针走的次数是慢指针的俩倍S快2k,S(慢k,而且快指针比慢指针多走一个环形这里可以验证快指针第一次超越慢指针不可能越过慢指针必定重合可自行画图解析 即k一圈的节点数也就是慢指针此时从第一节点出发走了一个环形节点数步数若此时让快指针从头节点出发慢指针从原位置出发俩指针每次都走一步快指针走a步到达入环的第一个节点那么慢指针是不是走ak次呢是不是可以认为慢指针先走a次,到达入环第一个节点然后再走k次一圈回到原位置呢。 代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {if(headNULL||head-nextNULL){return NULL;}ListNode* fasthead;ListNode*slowhead;do{slowslow-next;fastfast-next-next;}while((fast!NULLfast-next!NULLslow!fast));if(fastNULL||fast-nextNULL){return NULL;}if(slowfast){fasthead;}while(fast!slow){slowslow-next;fastfast-next;}return fast;
}
三、俩俩交换链表中的节点 24.俩俩交换链表中的节点 解法一递归思想 1将大化小将整个链表俩俩交换节点化为前俩个节点交换后指向后面整体俩俩交换的部分链表以此层层递进将整体化为部分 2出口最后剩一个节点或NULL,则返回此节点 创造新的头节点为链表的头节点的第二个节点让原来的头节点指向后面交换返回的节点让新头节点指向原头节点返回新头节点 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* swapPairs(struct ListNode* head) {if(headNULL||head-nextNULL){return head;}ListNode* newheadhead-next;head-nextswapPairs(newhead-next);newhead-nexthead;return newhead;
} 解法二迭代思想 创造一个哑节点为node,紧跟后面的节点为node1和node2,每次交换node1和node2的位置然后node走到交换后node1的位置继续交换后面俩个节点的位置直到后面没有节点或只有一个节点 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* swapPairs(struct ListNode* head) {if(headNULL||head-nextNULL){return head;}ListNode*node(ListNode*)malloc(sizeof(ListNode));ListNode*tmpnode;tmp-nexthead;while(tmp-next!NULLtmp-next-next!NULL){ListNode*node1tmp-next;ListNode*node2tmp-next-next;node1-nextnode2-next;node2-nextnode1;tmp-nextnode2;tmpnode1;}return node-next;
}
四、排序链表
148.排序链表题目链接 思路 用一个数组存储链表的所有数据 然后对数组进行快排 然后将数据填入链表 返回即可 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/int compare(const void *e1,const void *e2){return *((int*)e1)-*((int*)e2);}typedef struct ListNode ListNode;
struct ListNode* sortList(struct ListNode* head) {if(headNULL||head-nextNULL){return head;}//至少俩个节点int arr[50000];ListNode*pcurhead;int i0;while(pcur){arr[i]pcur-val;i;pcurpcur-next;}qsort(arr,i,sizeof(int),compare);pcurhead;for(int j0;ji;j){pcur-valarr[j];pcurpcur-next;}return head;
}
