C他妈了，老子不信搞不完这差不多两百题，冲他妈地

c剑指offer day1

文章目录

• c剑指offer day1
• • • • [剑指 Offer 24. 反转链表](https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/) **JZ6** **从尾到头打印链表**
      • **JZ25** **合并两个排序的链表**
      • **JZ52 两个链表的第一个公共结点**
      • **JZ23** **链表中环的入口结点**
      • **JZ22** **链表中倒数最后k个结点**（同反轉鏈表，都用stack的思想）
      • **JZ35** **复杂链表的复制**
      • **JZ76** **删除链表中重复的结点**
      • **JZ18** **删除链表的节点**
      • **JZ55** **二叉树的深度**（遞歸）
      • **JZ77** **按之字形顺序打印二叉树**（迭代）
      • **JZ54** **二叉搜索树的第k个节点**（遞歸）
      • **JZ7** **重建二叉树**
      • **JZ26** **树的子结构 ** (難點)
      • **JZ27** **二叉树的镜像**
• 刷題總結
• • • • [剑指 Offer 24. 反转链表](https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/) [剑指 Offer 06. 从尾到头打印链表](https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/)
      • [剑指 Offer 25. 合并两个排序的链表](https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/)
      • [剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)
      • [剑指 Offer II 022. 链表中环的入口节点](https://leetcode.cn/problems/c32eOV/)
      • [剑指 Offer 22. 链表中倒数第k个节点](https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)

剑指 Offer 24. 反转链表 JZ6 从尾到头打印链表

• 使用stack全部入棧，然後再出棧鏈接

JZ25 合并两个排序的链表

• 使用一個指針， 一個虛擬頭節點
• 每一次比較兩個鏈表開頭，哪個大cur.next就指向哪個，然後被指的跳一個，結束前，cur也跳一個

JZ52 两个链表的第一个公共结点

• 兩個cur在上，一個在下
• 每次兩個都++，判斷是否相等
• 如果到尾了，開始遍歷對面的鏈表

原理：

兩條鏈：相交在中間

size: 3–>2

size: 1–>2

黨兩個指針相遇的時候，他們走的路程是相等的：

cur1: 3+2+1 = 6

cur2: 1+2+3 = 6

如果没有交点，那么相等的时候

JZ23 链表中环的入口结点

沒有環的話，指針最後會指向Null

有環情況：

• 利用快慢指針得出來相遇節點
• 得出后，快指針變成正常指針，和慢指針從頭遍歷，第二次相遇即入口點

JZ22 链表中倒数最后k个结点（同反轉鏈表，都用stack的思想）

JZ35 复杂链表的复制

即兩個指針域

方法：先遍歷第一遍得到正常指針域

第二遍使用move函數來讀取鏈表的第k個數，接到random域去即可

JZ76 删除链表中重复的结点

• 遇到有重複的節點

• 先保存節點值在一個臨時的temp

• 用while來循環隔斷鏈接

JZ18 删除链表的节点

這就是一個正常的刪除操作，條件是值相等

需要用一個前後指針來操作 prev cur

if(cur.val = val){cur = cur->next;//skipprev.next = cur;//linkcontinue;
}else{prev.next = cur;//linkcur = cur.next;//shiftprev = prev.next;//shift
}

JZ55 二叉树的深度（遞歸）

• 遞歸遍歷

JZ77 按之字形顺序打印二叉树（迭代）

• 使用兩個輔助stack

• 每一層在stack裏，出stack的時候，都按照左右左右，右左右左地交替遍歷孩子，壓入stack，待下一層使用

• 終止條件是兩個stack都遍歷空

JZ54 二叉搜索树的第k个节点（遞歸）

S1:

• 前序遍歷，找第k個

S2:

• 寫一個search的遞歸函數
• 直接在遞歸的過程當中，加入一個全局變量，count來統計目前位置的排位，如果排位count = val， 則直接返回所在結點的地址給res

JZ7 重建二叉树

前序中序重建二叉樹，規律：中序數組第一個，是前序數組的中間，以這個為中間劃分左右子數組

• 重點：使用遞歸函數，遞歸建樹

//函數傳入兩個子數組
//數組采用左右指針來包括：
// 左子樹：前序數組：pre.begin()+1  pre.begin()+1+i 中序數組：vin.begin() vin.begin()+i
// 右子樹：前序數組：pre.begin()+i+1 pre.end() 中序數組：vin.begin()+i+1 vin.end()
root->left = reConstructBinaryTree(leftpre, leftvin); root->right = reConstructBinaryTree(rightpre, rightvin); 

JZ26 **树的子结构 ** (難點)

方法：先想一個最簡單的比較函數recur()

• 先比較父節點，AB的值不等，false； A空，不匹配，也是false；B空，B是空樹，肯定匹配，返回true
• 再比較子節點，即recur(A.left,B.left) && recur(A.right,B.right)

class Solution {public boolean isSubStructure(TreeNode A, TreeNode B) {return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));}boolean recur(TreeNode A, TreeNode B) {if(B == null) return true;if(A == null || A.val != B.val) return false;return recur(A.left, B.left) && recur(A.right, B.right);}
}作者：jyd
链接：https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。class Solution {public boolean isSubStructure(TreeNode A, TreeNode B) {if (B == null || A == null) {return false;}if (A.val == B.val && (helper(A.left, B.left) && helper(A.right, B.right))) {return true;}return isSubStructure(A.left, B) || isSubStructure(A.right, B);}private boolean helper(TreeNode root1, TreeNode root2) {if (root2 == null) {return true;}if (root1 == null) {return false;}if (root1.val == root2.val) {return helper(root1.left, root2.left) && helper(root1.right, root2.right);} else {return false;}}
}

JZ27 二叉树的镜像

自底而上的逐層交換左右節點。。。。其實自上而下也可以，反正每一個函數棧都會交換一次，順序不影響

class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if (root == nullptr) {return nullptr;}TreeNode* left = mirrorTree(root->left);TreeNode* right = mirrorTree(root->right);root->left = right;root->right = left;return root;}
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/solution/er-cha-shu-de-jing-xiang-by-leetcode-sol-z44i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

刷題總結

剑指 Offer 24. 反转链表 剑指 Offer 06. 从尾到头打印链表

• 存節點要帶* stack stk;
• 末尾节点的指针需要指向NULL（离谱）

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head==NULL) return NULL;stack stk;ListNode* dummy = new ListNode(-1);while(head){         stk.push(head);cout << stk.top()->val << endl;head = head->next;}ListNode* cur = dummy;while(!stk.empty()){cur->next = stk.top();cout << cur->next->val << endl;stk.pop();cur = cur->next;}cur->next = NULL; //末尾节点的指针需要指向NULLcout << dummy->next->val << endl;return dummy->next;}
};

class Solution {
public:vector reversePrint(ListNode* head) {stack stk;vector list;while(head){stk.push(head);head = head->next;}while(!stk.empty()){list.push_back(stk.top()->val);stk.pop();}return list;}
};

剑指 Offer 25. 合并两个排序的链表

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* dummy = new ListNode(-1);ListNode* cur = dummy;while(l1 && l2){if(l1->val < l2->val){cur->next = l1;l1 = l1->next;}else{cur->next = l2;l2 = l2->next;}cur = cur->next;}if(l1 == NULL) cur->next = l2;if(l2 == NULL) cur->next = l1;return dummy->next;}
};

剑指 Offer 52. 两个链表的第一个公共节点

• 空指针也是可以比较的，用于判断没有交点的情况

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *p1 = headA;ListNode *p2 = headB;while(p1 != p2){ //这里两个空指针也是可以比较的，用于判断没有交点的情况if(p1 != NULL) p1 = p1->next;elsep1 = headB;if(p2 != NULL)p2 = p2->next;elsep2 = headA;}return p1;
}

剑指 Offer II 022. 链表中环的入口节点

对于一些边界条件，可能考虑不清楚，需要一点点地加入判断进去，比如这题没有环情况怎么处理，建议重复问题可以使用哈希表

class Solution {
public:ListNode *detectCycle(ListNode *head) {if(!head) return NULL;ListNode *fast = head;ListNode *slow = head;if(slow->next == NULL) return NULL;if(fast->next->next == NULL) return NULL;fast = fast->next->next;slow = slow->next;while(fast != slow){if(fast->next == NULL || fast->next->next == NULL) return NULL; //尾巴没有衔接fast = fast->next->next;slow = slow->next;            }//find the meet positionslow = head;while(slow != fast){slow = slow->next;fast = fast->next;}return fast;}
};

剑指 Offer 22. 链表中倒数第k个节点

class Solution {
public:ListNode* getKthFromEnd(ListNode* head, int k) {stack stk;while(head){stk.push(head);head = head->next;}k--;//栈顶就是倒数第一个while(k--){stk.pop();}return stk.top();}
};