目录1、LeetCode203.移除链表元素203. 移除链表元素 - 力扣LeetCode解题思路C语言代码2.LeetCode206.反转链表206. 反转链表 - 力扣LeetCode解题思路C语言代码3.LeetCode876.链表的中间结点876. 链表的中间结点 - 力扣LeetCode解题思路C语言代码4.LeetCode面试题02.02.返回倒数第k个节点面试题 02.02. 返回倒数第 k 个节点 - 力扣LeetCode解题思路C语言代码5.LeetCode21.合并两个有序链表21. 合并两个有序链表 - 力扣LeetCode解题思路C语言代码6.LeetCode面试题02.01.分割链表面试题 02.04. 分割链表 - 力扣LeetCode解题思路C语言代码7.牛客OR36.链表的回文结构链表的回文结构_牛客题霸_牛客网解题思路C代码8.LeetCode16.相交链表160. 相交链表 - 力扣LeetCode解题思路C语言代码9.LeetCode141.环形链表1141. 环形链表 - 力扣LeetCode编辑解题思路C语言代码10.LeetCode142.环形链表2142. 环形链表 II - 力扣LeetCode解题思路C语言代码11.LeetCode138.随机链表的复制138. 随机链表的复制 - 力扣LeetCode解题思路C语言代码1、LeetCode203.移除链表元素203. 移除链表元素 - 力扣LeetCode解题思路创建一个新链表用来存储原链表中值不为val的结点。遍历原链表值不为val则尾插C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode *newHead NULL,*newTail NULL; struct ListNode *pcur head; while(pcur){ if(pcur - val ! val){ // pcur的val不等于val则插入 // 链表为空 if(newHead NULL){ newHead pcur; newTail pcur; }else{ // 链表不为空 newTail - next pcur; newTail newTail - next; } } pcur pcur - next; } if(newTail) newTail - next NULL; return newHead; }定义一个新链表定义一个指针pcur指向当前链表结点原链表当pcur指向的结点的val值和要删除的val值不同时则尾插进新链表中。尾插分为两种情况①当新链表中没有结点时直接将指向新链表的头和尾的指针都指向当前结点②当新链表中国有结点时将当前结点插入新链表中再将新链表的尾节点指向新的尾结点。最后将新链表的尾指针的next指向空再将新链表返回。2.LeetCode206.反转链表206. 反转链表 - 力扣LeetCode解题思路遍历链表将每一个结点的next指向原链表的上一个结点C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode *n1,*n2,*n3; if(head NULL) return head; n1 NULL,n2 head, n3 head - next; while(n2){ n2 - next n1; n1 n2; n2 n3; if(n3) n3 n3 - next; } return n1; }定义三个指针n1n2n3。n1用来保存当前结点反转后的下一个结点n2用来指向当前结点n3用来保存反转前的下一个结点。先将n1指向NULLn2指向头结点n3指向头结点的下一个结点。当n2指向的结点当前结点不为空时将当前结点的next指向n1反转后的下一个结点再将n1n2n3如果n3不为空向后移动一位。重复这一步骤直到n2指向NULL当前结点为空当n2指向空时n1指向反转后的链表的头结点返回n1。3.LeetCode876.链表的中间结点876. 链表的中间结点 - 力扣LeetCode解题思路快慢指针快指针走两步慢指针走一步。当快指针指向空时慢指针指向的结点就是链表的中间结点。C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { struct ListNode *fast,*slow; fast head; slow head; while(fast fast - next){ fast fast - next - next; slow slow - next; } return slow; }4.LeetCode面试题02.02.返回倒数第k个节点面试题 02.02. 返回倒数第 k 个节点 - 力扣LeetCode解题思路快慢指针快指针先走k步然后快慢指针同时走。由于快指针比慢指针快k步所以当快指针指向空时慢指针指向的就是倒数第k个结点C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ int kthToLast(struct ListNode* head, int k) { struct ListNode *fast head, *slow head; while (k--) { fast fast-next; } while (fast) { fast fast-next; slow slow-next; } return slow-val; }5.LeetCode21.合并两个有序链表21. 合并两个有序链表 - 力扣LeetCode解题思路定义两个指针分别遍历两个链表将两个指针指向的节点中val值较小的尾插进新链表中最后将新链表返回C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode *l1 list1,*l2 list2; struct ListNode *newHead NULL,*newTail NULL; if(l1 NULL)return l2; if(l2 NULL)return l1; while(l1 l2){ if(l1 - val l2 - val){ // l1尾插 if(newHead NULL){ newHead l1; newTail l1; }else{ newTail - next l1; newTail newTail - next; } l1 l1 - next; }else{ // l2尾插 if(newHead NULL){ newHead l2; newTail l2; }else{ newTail - next l2; newTail newTail - next; } l2 l2 - next; } } if(l1 NULL){ newTail - next l2; }else if(l2 NULL){ newTail - next l1; } return newHead; }当l1和l2中有一个为空时直接返回另一个链表。当l1和l2均不为空时遍历并将较小的结点尾插进新链表。当一个链表中的结点全部插入新链表后直接将另一个链表的剩余结点尾插到新链表中。最后将新链表返回。6.LeetCode面试题02.01.分割链表面试题 02.04. 分割链表 - 力扣LeetCode解题思路定义两个新链表一个less一个great遍历原链表将原链表中val值比x小的结点插入到less链表中val值比x大的插入到great链表中最后将great最后一个结点的next指向空并将less和great连接起来。C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* partition(struct ListNode* head, int x) { if(head NULL){ return head; } struct ListNode * lessHead (struct ListNode*)malloc(sizeof(struct ListNode)),*lessTail lessHead; struct ListNode * greaterHead (struct ListNode*)malloc(sizeof(struct ListNode)),*greaterTail greaterHead; struct ListNode* pcur head; while(pcur){ if(pcur - val x){ lessTail - next pcur; lessTail lessTail - next; }else{ greaterTail - next pcur; greaterTail greaterTail - next; } pcur pcur - next; } greaterTail - next NULL; lessTail - next greaterHead - next; struct ListNode* ret lessHead - next; free(lessHead); lessHead NULL; free(greaterHead); greaterHead NULL; return ret; }7.牛客OR36.链表的回文结构链表的回文结构_牛客题霸_牛客网解题思路将链表的后半部分反转两个指针分别从开头和中间开始走当两个指针指向的结点的val值不同时返回false当从中间开始走的结点走到NULL时说明原链表为回文结构返回trueC代码/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ #include iterator class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here if(A NULL){ return false; } struct ListNode* fast A,*slow A; while(fast fast-next){ fast fast - next - next; slow slow - next; } struct ListNode* pcur NULL, *next slow; while(slow){ next slow-next; slow - next pcur; pcur slow; slow next; } next A; while(pcur){ if(next-val ! pcur-val){ return false; } next next - next; pcur pcur - next; } return true; } };8.LeetCode16.相交链表160. 相交链表 - 力扣LeetCode解题思路遍历两个链表判断两个链表是否相交两个链表的尾结点地址是否相等同时记录两个链表的长度。如果两个链表不相交则返回NULL。如果相交求出两个链表长度的差值gap让较长的链表上的指针先走gap步再让两个链表上的指针同时走。当两个指针相遇时即为相交的起始节点。C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { int countA 1, countB 1,num 0; struct ListNode * pcurA headA,*pcurB headB; while(pcurA - next){ countA ; pcurA pcurA - next; } while(pcurB - next){ countB ; pcurB pcurB - next; } if(pcurA ! pcurB){ return NULL; } // 假设法假设A长B短再比较长度假设错误就修正 int gap abs(countA - countB); struct ListNode *longList headA,*shortList headB; if(countA countB){ longList headB; shortList headA; } while(gap){ longList longList - next; gap --; } while(shortList){ if(longList ! shortList){ shortList shortList - next; longList longList - next; continue; } return shortList; } return NULL; }9.LeetCode141.环形链表1141. 环形链表 - 力扣LeetCode解题思路定义一组快慢指针快指针走两步同时慢指针走一步。如果快指针走到NULL说明链表没有环返回false如果快慢指针在某一个结点相遇则链表一定有环返回trueC语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode *fast head,*slow head; while(fast fast - next){ fast fast - next - next; slow slow - next; if(fast slow){ return true; } } return false; }10.LeetCode142.环形链表2142. 环形链表 II - 力扣LeetCode解题思路首先判断链表是否有环如果没有环直接返回NULL如果有环就让两个指针分别从快慢指针相遇的结点和链表的头节点开始同时走。两个指针相遇的结点即为链表开始入环的第一个节点。C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *fast head,*slow head; while(fast fast - next){ fast fast - next - next; slow slow - next; if(fast slow){ struct ListNode *meet slow; while(meet ! head){ meet meet - next; head head - next; } return meet; } } return NULL; }11.LeetCode138.随机链表的复制138. 随机链表的复制 - 力扣LeetCode解题思路复制链表的每个结点插入到被复制的结点之后。将复制出的新结点的random指向原结点的random-next。最后将复制出的结点全部尾插到新的头结点后返回新的头结点。C语言代码/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { struct Node* pcur head; while(pcur){ struct Node* copy (struct Node*)malloc(sizeof(struct Node)); copy - val pcur - val; copy - next pcur - next; pcur - next copy; pcur copy - next; } pcur head; while(pcur){ struct Node* copy pcur - next; if(pcur - random NULL){ copy - random NULL; }else{ copy - random pcur - random - next; } pcur copy - next; } pcur head; struct Node* copyHead NULL, *copyTail NULL; while(pcur){ struct Node* copy pcur - next; struct Node* next copy - next; if(copyTail NULL){ copyTail copyHead copy; }else{ copyTail - next copy; copyTail copyTail - next; } pcur - next next; pcur next; } return copyHead; }
【数据结构】链表OJ
目录1、LeetCode203.移除链表元素203. 移除链表元素 - 力扣LeetCode解题思路C语言代码2.LeetCode206.反转链表206. 反转链表 - 力扣LeetCode解题思路C语言代码3.LeetCode876.链表的中间结点876. 链表的中间结点 - 力扣LeetCode解题思路C语言代码4.LeetCode面试题02.02.返回倒数第k个节点面试题 02.02. 返回倒数第 k 个节点 - 力扣LeetCode解题思路C语言代码5.LeetCode21.合并两个有序链表21. 合并两个有序链表 - 力扣LeetCode解题思路C语言代码6.LeetCode面试题02.01.分割链表面试题 02.04. 分割链表 - 力扣LeetCode解题思路C语言代码7.牛客OR36.链表的回文结构链表的回文结构_牛客题霸_牛客网解题思路C代码8.LeetCode16.相交链表160. 相交链表 - 力扣LeetCode解题思路C语言代码9.LeetCode141.环形链表1141. 环形链表 - 力扣LeetCode编辑解题思路C语言代码10.LeetCode142.环形链表2142. 环形链表 II - 力扣LeetCode解题思路C语言代码11.LeetCode138.随机链表的复制138. 随机链表的复制 - 力扣LeetCode解题思路C语言代码1、LeetCode203.移除链表元素203. 移除链表元素 - 力扣LeetCode解题思路创建一个新链表用来存储原链表中值不为val的结点。遍历原链表值不为val则尾插C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode *newHead NULL,*newTail NULL; struct ListNode *pcur head; while(pcur){ if(pcur - val ! val){ // pcur的val不等于val则插入 // 链表为空 if(newHead NULL){ newHead pcur; newTail pcur; }else{ // 链表不为空 newTail - next pcur; newTail newTail - next; } } pcur pcur - next; } if(newTail) newTail - next NULL; return newHead; }定义一个新链表定义一个指针pcur指向当前链表结点原链表当pcur指向的结点的val值和要删除的val值不同时则尾插进新链表中。尾插分为两种情况①当新链表中没有结点时直接将指向新链表的头和尾的指针都指向当前结点②当新链表中国有结点时将当前结点插入新链表中再将新链表的尾节点指向新的尾结点。最后将新链表的尾指针的next指向空再将新链表返回。2.LeetCode206.反转链表206. 反转链表 - 力扣LeetCode解题思路遍历链表将每一个结点的next指向原链表的上一个结点C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode *n1,*n2,*n3; if(head NULL) return head; n1 NULL,n2 head, n3 head - next; while(n2){ n2 - next n1; n1 n2; n2 n3; if(n3) n3 n3 - next; } return n1; }定义三个指针n1n2n3。n1用来保存当前结点反转后的下一个结点n2用来指向当前结点n3用来保存反转前的下一个结点。先将n1指向NULLn2指向头结点n3指向头结点的下一个结点。当n2指向的结点当前结点不为空时将当前结点的next指向n1反转后的下一个结点再将n1n2n3如果n3不为空向后移动一位。重复这一步骤直到n2指向NULL当前结点为空当n2指向空时n1指向反转后的链表的头结点返回n1。3.LeetCode876.链表的中间结点876. 链表的中间结点 - 力扣LeetCode解题思路快慢指针快指针走两步慢指针走一步。当快指针指向空时慢指针指向的结点就是链表的中间结点。C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { struct ListNode *fast,*slow; fast head; slow head; while(fast fast - next){ fast fast - next - next; slow slow - next; } return slow; }4.LeetCode面试题02.02.返回倒数第k个节点面试题 02.02. 返回倒数第 k 个节点 - 力扣LeetCode解题思路快慢指针快指针先走k步然后快慢指针同时走。由于快指针比慢指针快k步所以当快指针指向空时慢指针指向的就是倒数第k个结点C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ int kthToLast(struct ListNode* head, int k) { struct ListNode *fast head, *slow head; while (k--) { fast fast-next; } while (fast) { fast fast-next; slow slow-next; } return slow-val; }5.LeetCode21.合并两个有序链表21. 合并两个有序链表 - 力扣LeetCode解题思路定义两个指针分别遍历两个链表将两个指针指向的节点中val值较小的尾插进新链表中最后将新链表返回C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode *l1 list1,*l2 list2; struct ListNode *newHead NULL,*newTail NULL; if(l1 NULL)return l2; if(l2 NULL)return l1; while(l1 l2){ if(l1 - val l2 - val){ // l1尾插 if(newHead NULL){ newHead l1; newTail l1; }else{ newTail - next l1; newTail newTail - next; } l1 l1 - next; }else{ // l2尾插 if(newHead NULL){ newHead l2; newTail l2; }else{ newTail - next l2; newTail newTail - next; } l2 l2 - next; } } if(l1 NULL){ newTail - next l2; }else if(l2 NULL){ newTail - next l1; } return newHead; }当l1和l2中有一个为空时直接返回另一个链表。当l1和l2均不为空时遍历并将较小的结点尾插进新链表。当一个链表中的结点全部插入新链表后直接将另一个链表的剩余结点尾插到新链表中。最后将新链表返回。6.LeetCode面试题02.01.分割链表面试题 02.04. 分割链表 - 力扣LeetCode解题思路定义两个新链表一个less一个great遍历原链表将原链表中val值比x小的结点插入到less链表中val值比x大的插入到great链表中最后将great最后一个结点的next指向空并将less和great连接起来。C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* partition(struct ListNode* head, int x) { if(head NULL){ return head; } struct ListNode * lessHead (struct ListNode*)malloc(sizeof(struct ListNode)),*lessTail lessHead; struct ListNode * greaterHead (struct ListNode*)malloc(sizeof(struct ListNode)),*greaterTail greaterHead; struct ListNode* pcur head; while(pcur){ if(pcur - val x){ lessTail - next pcur; lessTail lessTail - next; }else{ greaterTail - next pcur; greaterTail greaterTail - next; } pcur pcur - next; } greaterTail - next NULL; lessTail - next greaterHead - next; struct ListNode* ret lessHead - next; free(lessHead); lessHead NULL; free(greaterHead); greaterHead NULL; return ret; }7.牛客OR36.链表的回文结构链表的回文结构_牛客题霸_牛客网解题思路将链表的后半部分反转两个指针分别从开头和中间开始走当两个指针指向的结点的val值不同时返回false当从中间开始走的结点走到NULL时说明原链表为回文结构返回trueC代码/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ #include iterator class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here if(A NULL){ return false; } struct ListNode* fast A,*slow A; while(fast fast-next){ fast fast - next - next; slow slow - next; } struct ListNode* pcur NULL, *next slow; while(slow){ next slow-next; slow - next pcur; pcur slow; slow next; } next A; while(pcur){ if(next-val ! pcur-val){ return false; } next next - next; pcur pcur - next; } return true; } };8.LeetCode16.相交链表160. 相交链表 - 力扣LeetCode解题思路遍历两个链表判断两个链表是否相交两个链表的尾结点地址是否相等同时记录两个链表的长度。如果两个链表不相交则返回NULL。如果相交求出两个链表长度的差值gap让较长的链表上的指针先走gap步再让两个链表上的指针同时走。当两个指针相遇时即为相交的起始节点。C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { int countA 1, countB 1,num 0; struct ListNode * pcurA headA,*pcurB headB; while(pcurA - next){ countA ; pcurA pcurA - next; } while(pcurB - next){ countB ; pcurB pcurB - next; } if(pcurA ! pcurB){ return NULL; } // 假设法假设A长B短再比较长度假设错误就修正 int gap abs(countA - countB); struct ListNode *longList headA,*shortList headB; if(countA countB){ longList headB; shortList headA; } while(gap){ longList longList - next; gap --; } while(shortList){ if(longList ! shortList){ shortList shortList - next; longList longList - next; continue; } return shortList; } return NULL; }9.LeetCode141.环形链表1141. 环形链表 - 力扣LeetCode解题思路定义一组快慢指针快指针走两步同时慢指针走一步。如果快指针走到NULL说明链表没有环返回false如果快慢指针在某一个结点相遇则链表一定有环返回trueC语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode *fast head,*slow head; while(fast fast - next){ fast fast - next - next; slow slow - next; if(fast slow){ return true; } } return false; }10.LeetCode142.环形链表2142. 环形链表 II - 力扣LeetCode解题思路首先判断链表是否有环如果没有环直接返回NULL如果有环就让两个指针分别从快慢指针相遇的结点和链表的头节点开始同时走。两个指针相遇的结点即为链表开始入环的第一个节点。C语言代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *fast head,*slow head; while(fast fast - next){ fast fast - next - next; slow slow - next; if(fast slow){ struct ListNode *meet slow; while(meet ! head){ meet meet - next; head head - next; } return meet; } } return NULL; }11.LeetCode138.随机链表的复制138. 随机链表的复制 - 力扣LeetCode解题思路复制链表的每个结点插入到被复制的结点之后。将复制出的新结点的random指向原结点的random-next。最后将复制出的结点全部尾插到新的头结点后返回新的头结点。C语言代码/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { struct Node* pcur head; while(pcur){ struct Node* copy (struct Node*)malloc(sizeof(struct Node)); copy - val pcur - val; copy - next pcur - next; pcur - next copy; pcur copy - next; } pcur head; while(pcur){ struct Node* copy pcur - next; if(pcur - random NULL){ copy - random NULL; }else{ copy - random pcur - random - next; } pcur copy - next; } pcur head; struct Node* copyHead NULL, *copyTail NULL; while(pcur){ struct Node* copy pcur - next; struct Node* next copy - next; if(copyTail NULL){ copyTail copyHead copy; }else{ copyTail - next copy; copyTail copyTail - next; } pcur - next next; pcur next; } return copyHead; }
