经典数据结构题目解析

链表

1.删除单链表的重复节点

遍历法

class Solution {
public:ListNode* removeDuplicateNodes(ListNode* head) {//先检查头节点是否为空，快速判断if (head == NULL) {return NULL;}  ListNode *current = head;//循环遍历检查每一个元素，如果有相同元素则去掉while (current) {ListNode *p = current;while (p->next) {if (p->next->val == current->val) {ListNode *toDelete = p->next;p->next = p->next->next;delete toDelete; // 释放内存} else {p = p->next;}}current = current->next;}return head;}
};

数组法：用一个数组指示，数组初始为0，一次遍历元素的值，出现就将数组对应值置1

2. 如何找出链表的倒数第K个元素

快慢指针法：快指针比慢指针快K个元素，当快指针指向末尾NULL时，此时慢指针指向倒数第K个元素。

class Solution {
public://快慢指针：空间换时间ListNode* trainingPlan(ListNode* head, int cnt) {ListNode* fast=head;ListNode* slow=head;while(cnt--){fast=fast->next;}while (fast){fast=fast->next;slow=slow->next;}return slow;}
};

 3. 如何找出链表的中间节点

双指针：快指针走两步，满指针走一步

class Solution {
public://双指针法ListNode* middleNode(ListNode* head) {ListNode* fast=head;ListNode* slow=head;while((fast!=NULL)&&(fast->next!=NULL)){fast=fast->next->next;slow=slow->next;}return slow;}
};

4. 反转链表

反转是逐个反转，例如反转1，2，3，4，5

先变成2，1，3，4，5

再3，2，1，4，5

依次直至最终反转

class Solution {
public://递归实现反转链表ListNode* trainningPlan(ListNode* head) {if(head==NULL || head->next==NULL){return head;}else{struct ListNode* mid=head;struct ListNode* lateer=mid->next;head =trainningPlan(lateer);lateer->next=mid;mid->next=NULL;return head;}}
};

5.环形链表  

快慢指针：总会相遇，一个两部一个一步

class Solution {
public://快慢指针，追到就是了bool hasCycle(ListNode *head) {ListNode *fast=head;ListNode *slow=head;while((fast!=NULL)&&(fast->next!=NULL)){fast=fast->next->next;slow=slow->next;if(fast==slow)return true;}return false;}
};

6. 单链表相交，如何求交点

移动相同的距离即是交点

class Solution {
public://这不是判断是否相交，比较简单，判断交点则AD+BD+DCListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *p=headA;ListNode *q=headB;while(p!=q){if(p!=NULL)p=p->next;elsep=headB;if(q!=NULL)q=q->next;elseq=headA;   }return q;}
};

7. 回文链表

找链表中间位置。将后半链表反转，依次和链表前一部分比较，看是否一致。

class Solution {
public:bool isPalindrome(ListNode* head) {if (head == NULL) return true;// 找到链表的中间节点ListNode* fast = head;ListNode* slow = head;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;}// 反转链表的后半部分ListNode* mid = slow;ListNode* prev = NULL;while (mid != NULL) {ListNode* nextTemp = mid->next;mid->next = prev;prev = mid;mid = nextTemp;}// 将slow指向反转后链表的头节点slow = prev;// 比较前半部分和反转后的后半部分是否相同fast = head;while (slow != NULL) {if (fast->val != slow->val) {return false;}fast = fast->next;slow = slow->next;}return true;}
};

8. 算法实现两个有序链表的合并

递归实现，返回两个链表最小值，

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1==NULL)return list2;if(list2==NULL)return list1;if(list1->val<list2->val){list1->next= mergeTwoLists(list1->next,list2);return list1;}else{list2->next=mergeTwoLists(list1,list2->next);return list2;}}
};

树

树代码的核心操作在于递归

1.求二叉树的深度

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int calculateDepth(TreeNode* root) {if(root ==NULL){return 0;}int Lenleft=calculateDepth(root->left);int lenright=calculateDepth(root->right);return Lenleft>lenright?Lenleft+1:lenright+1;}
};

2.如何判断二叉树是否相等

class Solution {
public://用某种遍历方法，存储成数组，遍历一棵树后，看数组是否相等void preOrder(struct TreeNode *root,int *arr,int *i){//用指针变量指示数组值的位置(*i)++;if(root==NULL){*(arr+*i)=0;return;}*(arr+*i)=root->val; preOrder(root->left,arr,i);preOrder(root->right,arr,i);}//前序遍历得到数组，再判断数组是否相等bool isSameTree(TreeNode* p, TreeNode* q) {int i,j;int arr1[1000],arr2[1000];memset(arr1,0,1000*sizeof(int));memset(arr2,0,1000*sizeof(int));if((p==NULL)&&(q==NULL))return 1;if((p==NULL)||(q==NULL))return 0;j=i=0;preOrder(p,arr1,&i);preOrder(q,arr2,&j);for(i=0;i<1000;i++){if(arr1[i]!=arr2[i]){return 0;}}return 1;}
};

3. 判断二叉树是否是平衡二叉树

挨个判断每个节点是否平衡，核心就是递归；

class Solution 
{
public:int deptmax(TreeNode* root){if(root==NULL){return 0;}int leftdept=deptmax(root->left);int rightdept=deptmax(root->right);return leftdept>rightdept?leftdept+1:rightdept+1;}//判断每一个节点的左右子树的深度，如何减少复杂度,实则判断meiyihbool isBalanced(TreeNode* root) {if(root==NULL){return true;}int leftdept=deptmax(root->left);int rightdept=deptmax(root->right);if(abs(leftdept-rightdept)<2==false){return false;}return abs(leftdept-rightdept)<2&&isBalanced(root->left)&&isBalanced(root->right);}
};

 数组

最大子序和

动态规划小问题，值得一看

class Solution {
public:int maxSubArray(vector<int>& nums) {int pre=0,maxans=nums[0];for(const auto &x:nums){pre =max(pre+x,x);maxans=max(maxans,pre);} return maxans;}
};

挨个判断将新元素加入子序列的影响。