【数据结构】经典习题
生活随笔
收集整理的這篇文章主要介紹了
【数据结构】经典习题
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
目錄
順序表：
習(xí)題1：給你一個數(shù)組 nums?和一個值 val，你需要 原地 移除所有數(shù)值等于?val?的元素，并返回移除后數(shù)組的新長度。
習(xí)題2：給你一個有序數(shù)組 nums ，請你 原地 刪除重復(fù)出現(xiàn)的元素，使每個元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度。
習(xí)題3：給你兩個有序整數(shù)數(shù)組?nums1 和 nums2，請你將 nums2 合并到?nums1?中，使 nums1 成為一個有序數(shù)組。
鏈表：
習(xí)題1：給你一個鏈表的頭節(jié)點(diǎn)?head?和一個整數(shù)?val?，請你刪除鏈表中所有滿足?Node.val == val?的節(jié)點(diǎn)，并返回?新的頭節(jié)點(diǎn)?。
習(xí)題2：給你單鏈表的頭節(jié)點(diǎn)?head?請你反轉(zhuǎn)鏈表并返回反轉(zhuǎn)后的鏈表。
習(xí)題3：給定一個頭結(jié)點(diǎn)為?head?的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。如果有兩個中間結(jié)點(diǎn)，則返回第二個中間結(jié)點(diǎn)。
習(xí)題4：輸入一個鏈表，輸出該鏈表中倒數(shù)第K個結(jié)點(diǎn)。
習(xí)題5：將兩個升序鏈表合并為一個新的?升序?鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的。
習(xí)題6：現(xiàn)有一鏈表的頭指針 ListNode*?pHead，給一定值x，編寫一段代碼將所有小于x的結(jié)點(diǎn)排在其余結(jié)點(diǎn)之前，且不能改變原來的數(shù)據(jù)順序，返回重新排列后的鏈表的頭指針。
習(xí)題7：對于一個鏈表，請?jiān)O(shè)計(jì)一個時間復(fù)雜度為O(n),額外空間復(fù)雜度為O(1)的算法，判斷其是否為回文結(jié)構(gòu)。給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結(jié)構(gòu)。保證鏈表長度小于等于900。
習(xí)題8：給你兩個單鏈表的頭節(jié)點(diǎn)?headA?和?headB?，請你找出并返回兩個單鏈表相交的起始節(jié)點(diǎn)。如果兩個鏈表沒有交點(diǎn)，返回?null?。
習(xí)題9：給定一個鏈表，判斷鏈表中是否有環(huán)。
? ?延伸問題：
習(xí)題10：給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)。?如果鏈表無環(huán)，則返回?null。
習(xí)題11：給你一個長度為?n?的鏈表，每個節(jié)點(diǎn)包含一個額外增加的隨機(jī)指針?random?，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。
順序表：
習(xí)題1：給你一個數(shù)組 nums?和一個值 val，你需要 原地 移除所有數(shù)值等于?val?的元素，并返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。
int removeElement(int* nums, int numsSize, int val) {int src = 0;int dst = 0;while (src < numsSize){if (nums[src] == val){src++;}else{nums[dst] = nums[src];src++;dst++;}}return dst; } int main() {int nums[] = { 3, 2, 2, 3, 3, 4 };int numsSize = sizeof(nums) / sizeof(nums[0]);int val = 3;int ret = removeElement(nums,numsSize,val);printf("%d\n",ret);return 0; }習(xí)題2：給你一個有序數(shù)組 nums ，請你 原地 刪除重復(fù)出現(xiàn)的元素，使每個元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。
int removeDuplicates(int* nums, int numsSize ) {int src = 0;int dest = 0;if (numsSize == 0)return 0;while (src < numsSize){if (nums[src] == nums[dest]){src++;}else{dest++;nums[dest] = nums[src];}}return dest+1; } int main() {int nums[] = { 1, 2, 3, 3, 4, 4, 4, 5 };int numsSize = sizeof(nums) / sizeof(nums[0]);int ret = removeDuplicates(nums, numsSize);printf("%d\n", ret);for (int i = 0; i < ret; i++){printf("%d\n", nums[i]);}return 0; }習(xí)題3：給你兩個有序整數(shù)數(shù)組?nums1 和 nums2，請你將 nums2 合并到?nums1?中，使 nums1 成為一個有序數(shù)組。
初始化?nums1 和 nums2 的元素?cái)?shù)量分別為?m 和 n 。你可以假設(shè)?nums1 的空間大小等于?m + n，這樣它就有足夠的空間保存來自 nums2 的元素。
void merge(int* nums1,int m,int* nums2, int n) {int i1 = m - 1;int i2 = n - 1;int dest = m + n - 1;//取大的給過去while (i1 >= 0 && i2 >= 0){if (nums1[i1] > nums2[i2]){nums1[dest] = nums1[i1];dest--;i1--;}else{nums1[dest] = nums2[i2];dest--;i2--;}}//如果是nums2結(jié)束，那就不用處理，因?yàn)槭Ｏ碌臄?shù)本來就是nums1里面//如果是nums1結(jié)束，就得把nums2的數(shù)據(jù)挪過去while (i2 >= 0){nums1[dest] = nums2[i2];dest--;i2--;} } int main() {int nums1[] = { 1, 2, 3, 0, 0, 0 };int nums2[] = { 4, 5, 6 };int nums1Size = sizeof(nums1) / sizeof(nums2[0]);int nums2Size = sizeof(nums1) / sizeof(nums2[0]);merge(nums1, 3,nums2,3);for (int i = 0; i < nums1Size; i++){printf(" %d",nums1[i]);}return 0; }鏈表：
習(xí)題1：給你一個鏈表的頭節(jié)點(diǎn)?head?和一個整數(shù)?val?，請你刪除鏈表中所有滿足?Node.val == val?的節(jié)點(diǎn)，并返回?新的頭節(jié)點(diǎn)?。
?思路2:代碼：
注意尾插時候的順序！?
//Definition for singly-linked list. struct ListNode {int val;struct ListNode *next; }; struct ListNode* removeElements(struct ListNode* head, int val) {if (head == NULL)return NULL;struct ListNode* newnode = NULL;struct ListNode* tail = NULL;//取不是val的節(jié)點(diǎn)尾插struct ListNode* cur = head;while (cur){struct ListNode* next = cur->next;if (cur->val == val){free(cur);}else{//尾插if (tail == NULL){newnode = tail = cur;}else{ //這里順序注意一下tail->next = cur;tail = cur;}}cur = next;}if (tail)tail->next = NULL;return newnode; } int main() {struct ListNode*n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*n4 = (struct ListNode*)malloc(sizeof(struct ListNode));n1->val = 1;n2->val = 2;n3->val = 3;n4->val = 7;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;struct ListNode* newnode = removeElements(n1, 7);while (newnode != NULL){printf("%d->",newnode->val);newnode = newnode->next;}printf("NULL\n");return 0; }習(xí)題2：給你單鏈表的頭節(jié)點(diǎn)?head?請你反轉(zhuǎn)鏈表并返回反轉(zhuǎn)后的鏈表。
方法1：
struct ListNode* reverseList(struct ListNode* head) {if (head == NULL)return head;struct ListNode*n1 = NULL;struct ListNode*n2 = NULL;struct ListNode*n3 = NULL;n1 = NULL;n2 = head;n3 = head->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n2->next;}return n1; }方法2：
struct ListNode* reverseList(struct ListNode* head) {if(head == NULL || head->next ==NULL)return head;struct ListNode* cur = head;struct ListNode* newhead = NULL;while(cur){struct ListNode* next= cur->next;cur->next = newhead;newhead = cur;//注意這行代碼別順序別對調(diào)了cur = next;}return newhead; }習(xí)題3：給定一個頭結(jié)點(diǎn)為?head?的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。如果有兩個中間結(jié)點(diǎn)，則返回第二個中間結(jié)點(diǎn)。
注意：這里有兩種情況，所以while里面要判斷2種情況?
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow;struct ListNode* fast;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}習(xí)題4：輸入一個鏈表，輸出該鏈表中倒數(shù)第K個結(jié)點(diǎn)。
注意：
1，當(dāng)K大于節(jié)點(diǎn)的個數(shù)的時候，會發(fā)生越界訪問，此時得加判斷條件
2，當(dāng)K等于0，不影響結(jié)果
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code hereif(k == 0)return NULL;struct ListNode*fast = NULL;struct ListNode*slow = NULL;slow = fast = pListHead;while(k--){if(fast == NULL)return NULL;fast = fast->next; }while(fast){slow = slow->next;fast = fast->next;}return slow; }習(xí)題5：將兩個升序鏈表合并為一個新的?升序?鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的。
思路：這里給了一個哨兵位頭結(jié)點(diǎn)，不存儲有效數(shù)據(jù)，方便尾插，處理完以后，記得刪掉?
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if (l1 == NULL)return l2;if (l2 == NULL)return l1;struct ListNode*n1 = l1;struct ListNode*n2 = l2;struct ListNode*newhead = NULL;struct ListNode*tail = NULL;//給一個哨兵位的頭節(jié)點(diǎn)，方便尾插，處理完以后，再刪掉newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode));/*if (n1->val < n2->val){newhead = tail = n1;n1 = n1->next;}else{newhead = tail = n2;n2 = n2->next;}*/while (n1 && n2){if (n1->val < n2->val){tail->next = n1;tail = n1;n1 = n1->next;}else{tail->next = n2;tail = n2;n2 = n2->next;}}if (n1)tail->next = n1;if (n2)tail->next = n2;struct ListNode* first = newhead->next;free(newhead);return first; }習(xí)題6：現(xiàn)有一鏈表的頭指針 ListNode*?pHead，給一定值x，編寫一段代碼將所有小于x的結(jié)點(diǎn)排在其余結(jié)點(diǎn)之前，且不能改變原來的數(shù)據(jù)順序，返回重新排列后的鏈表的頭指針。
思路：將比x大的數(shù)拿出來拼在一起，然后再將2個鏈表連接起來！
class Partition { public:ListNode* partition(ListNode* pHead, int x){// write code herestruct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail;lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*cur = pHead;while (cur){if (cur->val < x){lessTail->next = cur;lessTail = cur;}else{greaterTail->next = cur;greaterTail = cur;}cur = cur->next;}lessTail->next = greaterHead->next;struct ListNode*head = lessHead->next;free(lessHead);free(greaterHead);return head;} };思考：此處代碼哪里出問題了？
?
?關(guān)注邊界，一般鏈表的邊界就是頭尾，數(shù)組的話就是關(guān)注開始或者快結(jié)束的位置的處理！
greaterTail->next = NULL;習(xí)題7：對于一個鏈表，請?jiān)O(shè)計(jì)一個時間復(fù)雜度為O(n),額外空間復(fù)雜度為O(1)的算法，判斷其是否為回文結(jié)構(gòu)。給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結(jié)構(gòu)。保證鏈表長度小于等于900。
思路：創(chuàng)建一個數(shù)組!? ?問題：空間復(fù)雜度不滿足O(1)?
方法1：?
bool chkPalindrome(ListNode* A){// write code hereint a[900];struct ListNode* cur = A;int n = 0;while(cur){a[n++] = cur->val;cur = cur->next;}int left = 0;int right = n-1;while(left < right){if(a[left] != a[right]){return false;} left++;right--;}return true;}方法2：?
struct ListNode* FindMidNode(struct ListNode* phead){struct ListNode*slow;struct ListNode*fast;slow = fast = phead;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}struct ListNode* reverseList(struct ListNode* phead){struct ListNode*newhead = NULL;struct ListNode*cur = phead;while(cur){struct ListNode*next = cur->next;cur->next = newhead;newhead = cur;cur = next;}return newhead;}bool chkPalindrome(ListNode* A){// write code herestruct ListNode*mid = FindMidNode(A);struct ListNode*rhead = reverseList(mid);struct ListNode*head = A;while(head && rhead){if(head->val != rhead->val)return false;rhead = rhead->next;head = head->next;}return true;}習(xí)題8：給你兩個單鏈表的頭節(jié)點(diǎn)?headA?和?headB?，請你找出并返回兩個單鏈表相交的起始節(jié)點(diǎn)。如果兩個鏈表沒有交點(diǎn)，返回?null?。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curA = headA;struct ListNode *curB = headB;int lenA = 0;int lenB = 0;while (curA){lenA++;curA = curA->next;}while (curB){lenB++;curB = curB->next;}struct ListNode *longlist = headA;struct ListNode *shortlist = headB;if (lenA < lenB){longlist = headB;shortlist = headA;}int gap = abs(lenA - lenB);while (gap--){longlist = longlist->next;}while (longlist && shortlist){if (longlist == shortlist){return longlist;}longlist = longlist->next;shortlist = shortlist->next;}return NULL; }習(xí)題9：給定一個鏈表，判斷鏈表中是否有環(huán)。
如果鏈表中有某個節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。
如果鏈表中存在環(huán)，則返回 true 。 否則，返回 false 。
思路：快慢指針
bool hasCycle(struct ListNode *head) {struct ListNode *slow = head;struct ListNode *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){return true;}}return false; }延伸問題：
證明：fast一次走2步，slow一次走1步可以，fast一次走3，4 ，5步可以嗎？
總結(jié)：fast一次走x，slow一次走y步都是可以的，最重要的是，追趕過程中的步差x-y，步差是1，一定能追上，步差不是1就不一定能追上。這里如果fast一次走4，5，6等等同理
習(xí)題10：給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)。?如果鏈表無環(huán)，則返回?null。
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow= head;struct ListNode *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){struct ListNode *meet = slow;while(head != meet){head = head->next;meet = meet->next;}return meet;}}return NULL; }方法2：調(diào)用習(xí)題8的解法?：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curA = headA;struct ListNode *curB = headB;int lenA = 0;int lenB = 0;while (curA){lenA++;curA = curA->next;}while (curB){lenB++;curB = curB->next;}struct ListNode *longlist = headA;struct ListNode *shortlist = headB;if (lenA < lenB){longlist = headB;shortlist = headA;}int gap = abs(lenA - lenB);while (gap--){longlist = longlist->next;}while (longlist && shortlist){if (longlist == shortlist){return longlist;}longlist = longlist->next;shortlist = shortlist->next;}return NULL; }struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow= head;struct ListNode *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){struct ListNode *meet = slow;struct ListNode *next = meet->next;meet->next = NULL; //調(diào)用習(xí)題8的解法return getIntersectionNode(head,next);}}return NULL; }習(xí)題11：給你一個長度為?n?的鏈表，每個節(jié)點(diǎn)包含一個額外增加的隨機(jī)指針?random?，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。
struct Node* copyRandomList(struct Node* head) {if(head == NULL)return NULL;//拷貝節(jié)點(diǎn)掛在原節(jié)點(diǎn)的后面struct Node*cur = head;while(cur){struct Node*next = cur->next;struct Node*copy = (struct Node*)malloc(sizeof( struct Node));copy->val = cur->val;cur->next = copy;copy->next = next;cur = next;}//置randomcur = head;while(cur){struct Node*copy = cur->next;if(cur->random)copy->random = cur->random->next;elsecopy->random = NULL; cur = copy->next;}//3.把原鏈表的節(jié)點(diǎn)解下來，尾插到新鏈表struct Node*copyhead=NULL;struct Node*copytail=NULL;copyhead = copytail = (struct Node*)malloc(sizeof(struct Node));cur = head;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;copytail->next = copy;copytail = copy;cur->next = next;cur = next;}struct Node* del = copyhead;copyhead = copyhead->next;free(del);return copyhead; }總結(jié)
以上是生活随笔為你收集整理的【数据结构】经典习题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： DotSoft.C3DTools.v7.
- 下一篇： 懒人的法宝——办公自动化！