网站界面怎么做,网站注册商是什么,wordpress后台界面模板,西安工程建设信息网目录 1. 移除链表元素2. 反转链表2.1反转指针法2.2 头插法 3. 合并两个有序链表4. 分隔链表5. 环形链表6. 链表的中间节点7. 链表中倒数第K个节点8. 相交链表9. 环形链表的约瑟夫问题10. 链表的回文结构 1. 移除链表元素 思路1#xff1a;遍历原链表#xff0c;将 val 所在的… 目录 1. 移除链表元素2. 反转链表2.1反转指针法2.2 头插法 3. 合并两个有序链表4. 分隔链表5. 环形链表6. 链表的中间节点7. 链表中倒数第K个节点8. 相交链表9. 环形链表的约瑟夫问题10. 链表的回文结构 1. 移除链表元素 思路1遍历原链表将 val 所在的节点释放掉。(太麻烦)
思路2创建新链表再遍历原链表找到不为 val 的节点尾插到新链表。 思路1代码实现如下
注意 1.当链表为空时直接返回NULL即可。 2.当尾插上最后一个有效节点时此时它的 next 可能还与最后一个节点相链接一定要断开 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {if (head NULL)return NULL;//创建一个新链表ListNode* newHead, * newTail;newHead newTail NULL;ListNode* pcur head;//遍历原链表找不为val的节点尾插while (pcur){ListNode* next pcur-next;if (pcur-val ! val){//没有一个节点if (newHead NULL){newHead newTail pcur;}else{//有一个节点以上newTail-next pcur;newTail newTail-next;}}pcur next;}if (newTail)newTail-next NULL;return newHead;}2. 反转链表 2.1反转指针法
思路定义三个变量 n1n2n3根据它们的指向关系进行迭代。
代码实现如下
注意 1.当链表为空时直接返回NULL即可。 2.在迭代过程中别忘记判断 n3 防止对空指针解引用。 3.注意循环结束的条件当 n2 为空时n1 指向反转后的头此时循环结束。
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if (head NULL)return NULL;ListNode* n1, * n2, * n3;n1 NULL, n2 head, n3 n2-next;while (n2){n2-next n1;n1 n2;n2 n3;if (n3)n3 n3-next;}return n1;
}2.2 头插法
思路创建一个新链表遍历原链表依次取下原链表的每一个节点头插到新链表中。
代码实现如下
注意 1.当链表为空时直接返回NULL即可。 2.头插时可以不用判断没有节点和有节点的情况。 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if (head NULL)return NULL;ListNode* newHead, * newTail;newHead newTail NULL;ListNode* pcur head;//一个一个拿下来头插while (pcur){ListNode* next pcur-next;pcur-next newHead;newHead pcur;pcur next;}return newHead;
}3. 合并两个有序链表 思路创建一个带哨兵位的新链表遍历两个原链表比较两个节点的值哪个小就先尾插到新链表中。
代码实现如下
注意 1.当其中一个链表为空时返回另一个链表即可。 2.创建哨兵位节点方便尾插。 3.注意循环结束条件当其中有一个链表走完时跳出循环。 4.剩下的没走完的那个链表直接链接到后面。不需要用循环链接因为它们本来就是连在一起的。 5.别忘记释放释放哨兵位节点释放前要保存下一个节点。 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {ListNode* n1, * n2;n1 list1;n2 list2;if (n1 NULL)return n2;if (n2 NULL)return n1;//创建哨兵位节点ListNode* phead (ListNode*)malloc(sizeof(ListNode));ListNode* newHead, * newTail;newHead newTail phead;while (n1 n2){//比较两个链表中数据的大小谁小就先尾插到新链表if (n1-val n2-val){newTail-next n1;n1 n1-next;newTail newTail-next;}else{newTail-next n2;n2 n2-next;newTail newTail-next;}}if (n1)newTail-next n1;if (n2)newTail-next n2;ListNode* ret newHead-next;free(newHead);return ret;}4. 分隔链表 思路创建两个带哨兵位的新链表 less 和 greater 。遍历原链表把小于x 的节点尾插到 less 链表中把大于等于x 的节点尾插到greater 链表中。最后把 less 链表中的尾结点的 next 链接到 greater链表中的头结点上。 代码实现如下
注意 1.当链表尾空时直接返回NULL即可。
2.有可能存在greater 链表中的最后一个结点与原链表中的最后一个结点仍然相链接的情况一定要断开 typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {if (head NULL)return NULL;ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;ListNode* pcur head;//创建哨兵位节点方便尾插lessHead lessTail (ListNode*)malloc(sizeof(ListNode));greaterHead greaterTail (ListNode*)malloc(sizeof(ListNode));lessTail-next NULL;greaterTail-next NULL;while (pcur){if (pcur-val x){lessTail-next pcur;lessTail lessTail-next;}else{greaterTail-next pcur;greaterTail greaterTail-next;}pcur pcur-next;}lessTail-next greaterHead-next;greaterTail-next NULL;return lessHead-next;}5. 环形链表 这是一个非常经典的例题它要用上一种非常经典的算法快慢指针法。
定义一个 slow 变量fast 变量从链表的头结点开始slow 每次走一步fast 每次走两步当 slow 进入环中时fast 开始追逐。若成环则必会在环内的某处相遇否则 fast 或是 fast-next 最后会走到NULL。
代码实现如下
注意 1.当链表节点个数为偶数个时若不成环最终 fast NULL。 当链表节点个数为奇数个时若不成环最终 fast-next NULL.
2.循环条件 fast fast-next 的位置不能交换。因为当为偶数个节点fast走到NULL时如果是 fast-next fast 那就是先执行 fast-next 对空指针解引用错误 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {ListNode* slow, * fast;slow fast head;while (fast fast-next){slow slow-next;fast fast-next-next;if (fast slow)return true;}return false;
}6. 链表的中间节点 也要用快慢指针法。也要分两种情况
代码实现如下
注意 循环条件 fast fast-next 的位置不能交换。因为当为偶数个节点fast走到NULL时如果是 fast-next fast 那就是先执行 fast-next 对空指针解引用错误 typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head) {ListNode* slow head;ListNode* fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}return slow;}7. 链表中倒数第K个节点 思路 (1) fast 先走 k 步 (2) slow 和 fast 再一起走当 fast NULL 时slow 就是倒数第 k 个节点。
代码实现如下
注意 当 k 大于链表长度时fast 会走到 NULL 不能对空指针解引用直接返回 NULL。 typedef struct ListNode ListNode;
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {ListNode* fast ,*slow;fast slow pHead;//fast先走K步while(k--){//K大于链表长度时直接返回NULLif(fast NULL){return NULL;}fast fast-next;}//再两者一起走while(fast){fast fast-next;slow slow-next;}return slow;}8. 相交链表 首先要明确什么是相交链表
思路1暴力求解时间复杂度O(N*N) 依次取A链表中的每个节点跟B链表中的所有节点比较。如果有相同地址的节点则相交第一次相同地址的节点就是交点否则就不相交。
思路2时间复杂度O(N) (1) 先找到两个链表的尾,同时计算出两个链表的长度 (2) 求出长度差 (3) 判断哪个是长链表 (4) 让长链表先走长度差步 (5) 最后长短链表一起走直到找到交点。
思路2代码实现如下
注意 要注意步骤(3)中判断长短链表的巧妙方法。可以避免写重复代码。
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode* TailA,*TailB;TailA headA;TailB headB;//找尾同时计算长度int lenA 0;int lenB 0;while(TailA-next){TailA TailA-next;lenA;}while(TailB-next){TailB TailB-next;lenB;}//不相交if(TailA ! TailB){return NULL;}//求出长度差int gap abs(lenA - lenB);//判断哪个是长链表ListNode* longList headA;//先默认A是长链表ListNode* shortList headB;if(lenA lenB){shortList headA;longList headB;}//让长链表走长度差步while(gap--){longList longList-next;}//最后长短链表一起走找交点while(longList ! shortList){longList longList-next;shortList shortList-next;}return longList;}9. 环形链表的约瑟夫问题 思路 首先要创建一个循环链表定义一个计数器 count 用于数数再遍历循环链表当结点的 val count 时就杀死即销毁该节点。
代码实现如下
注意 要学习创建循环链表的方法
typedef struct ListNode ListNode;//创建节点ListNode* BuyNode(int x){ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if(newnode NULL){exit(-1);}newnode-val x;newnode-next NULL;return newnode;}//1.创建循环链表ListNode* Createnodecircle(int n){ListNode* phead BuyNode(1);ListNode* ptail phead;for(int i2;in;i){ptail-next BuyNode(i);ptail ptail-next;}//尾连头成环ptail-next phead;return ptail;}int ysf(int n, int m ) {ListNode* prev Createnodecircle(n);ListNode* pcur prev-next;//开始数数int count 1;while(pcur-next!prev-next){if(count m){prev-next pcur-next;free(pcur);pcur prev-next;count 1;}else{prev pcur;pcur pcur-next;count;}}return pcur-val;}
10. 链表的回文结构 这个题在牛客网中不能用C语言实现我们可以选C因为C是兼容C的在C中可以使用C的语法。 思路 (1) 找到链表的中间节点 (2) 把中间节点后面的链表进行逆置 (3) 最后把逆置后的链表的值与中间节点之前的链表的值进行比较若所有节点相等则是回文链表否则不是。有一个链表结束则比较结束。
代码实现如下
注意 逆置完之后中间节点与前一个结点的链接可以不用断开因为就算链接在一起也不影响判断。若强行断开徒增麻烦。 //找中间结点
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow head;struct ListNode* fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}return slow;}//对中间结点之后的链表进行逆置
struct ListNode* reverseList(struct ListNode* head) {if (head NULL)return NULL;struct ListNode* n1, * n2, * n3;n1 NULL, n2 head, n3 n2-next;while (n2){n2-next n1;n1 n2;n2 n3;if (n3)n3 n3-next;}return n1;
}class PalindromeList {public:bool chkPalindrome(ListNode* A) {struct ListNode* mid middleNode(A);struct ListNode* rHead reverseList(mid);struct ListNode* curA A;struct ListNode* curR rHead;//把逆置后的链表与中间结点之前的链表进行比较while(curA curR){if(curA-val ! curR-val){return false;}else{curA curA-next;curR curR-next;}}return true;}};
