【数据结构】链表（leetcode）
目录
① 203.移除链表元素
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { ListNode*newHead = NULL, *newTail = NULL; ListNode*pcur = head; while(pcur != NULL) { if(pcur->val != val) { if(newHead == NULL) { //将新链表的头尾指针指向原链表头节点 newHead = newTail = pcur; } else { newTail->next = pcur; newTail = newTail->next; } } pcur = pcur->next; } if(newTail != NULL) { newTail->next = NULL; } return newHead; }
② 206.反转链表
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev = NULL;//哨兵位 struct ListNode* cur = head;//头节点 while (cur) { // 哨兵位（prev） 节点1（cur） 节点2（cur->next） struct ListNode* next = cur->next;//创建一个中间节点 //开始改变链表的方向 cur->next = prev;//节点2先指向节点1的前一个节点 prev = cur;//哨兵位往后移动 cur = next;//节点1向后移动 } return prev; }
③ 876.链表的中间节点
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ 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; }
④ 返回倒数第k个节点（面试题）
/** * 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; //本题采用的是相对法： // fast先运动k个节点 // 假设该链表的节点个数是 m+k 个 // 则先走k个节点，剩下fast指针到null指针时，即走了m个节点 // 此时，slow指针就剩余k个节点 while(k--){ fast = fast->next; } while(fast != NULL){ slow = slow->next; fast = fast->next; } return slow->val; }
⑤ 21.合并两个有序链表
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1 == NULL) { return list2; }if(list2 == NULL) { return list1; } struct ListNode* l1 = list1; struct ListNode* l2 = list2; struct ListNode* newHead, *newTail; newHead = newTail = NULL; while(l1 && l2) { //比大小 if(l1->val < l2->val) { if(newHead == NULL) { newHead = newTail = l1; } else { newTail->next = l1; newTail = newTail->next; } l1 = l1->next; } else { if(newHead == NULL) { newHead = newTail = l2; }else { newTail->next = l2; newTail = newTail->next; } l2 = l2->next; } } if(l1) { newTail->next = l1; } if(l2) { newTail->next = l2; } return newHead; }
⑥ 160.相交链表
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA, *curB = headB; int lenA = 1, lenB = 1; while(curA->next){ curA = curA->next; ++lenA; } while(curB->next){ curB = curB->next; ++lenB; } if(curA != curB){ return NULL; } //假设法 int gap = abs(lenA - lenB); struct ListNode* longList = headA, *shortList = headB; if(lenB > lenA){ longList = headB; shortList = headA; }` while(gap--){ longList = longList->next; } while(longList != shortList){ longList = longList->next; shortList = shortList->next; } return longList; }
⑦ 138.随机链表的复制（深拷贝）
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; while(cur){ struct Node * copy = (struct Node*)malloc(sizeof(struct Node)); //赋值 copy->val = cur->val; //将copy链表插入原链表中 copy->next = cur->next; cur->next = copy; //cur向后移动 cur = copy->next; } //将copy链表中random指针的指向与原链表中的指针对调 cur = head; while(cur){ struct Node* copy = cur->next; if(cur->random == NULL){ copy->random = NULL; } else{ copy->random = cur->random->next; } cur = copy->next; } cur = head; struct Node* copyHead = NULL,* copyTail =NULL; while(cur){ struct Node* copy = cur->next; if(copyTail == NULL) { copyHead = copyTail = copy; }else { copyTail->next = copy; copyTail = copyTail->next; } //cur向后移动 cur = copy->next; } return copyHead; }
