題目描述

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

解析：p1,p2保持k-1的距離，當(dāng)p1指向鏈表尾時(shí)，p2正好指向倒數(shù)第k個(gè)結(jié)點(diǎn)

/* struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {} };*/ class Solution { public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {//p1,p2保持k-1的距離，當(dāng)p1指向鏈表尾時(shí)，p2正好指向倒數(shù)第k個(gè)結(jié)點(diǎn)if( pListHead==NULL || k==0 )//空鏈表 返回NULL； k從1開始計(jì)數(shù) k=0時(shí)返回NULLreturn NULL;struct ListNode *p1;struct ListNode *p2;p1=pListHead;p2=pListHead;int i;for(i=0;i<k-1;i++){if(p1->next!=NULL)p1=p1->next;else//k超過鏈表長(zhǎng)度return NULL;}while(p1->next!=NULL){p1=p1->next;p2=p2->next;}return p2;} };

題目描述

輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素。

解析：curNode保存當(dāng)前結(jié)點(diǎn)，preNode保存已遍歷過的反轉(zhuǎn)好的鏈表的頭結(jié)點(diǎn)，newList作最后反轉(zhuǎn)好的鏈表頭。當(dāng)curNode不是指向鏈表尾時(shí)，先保存鏈表nextNode值，使curNode->next指向preNode，preNode再保存curNode，最后恢復(fù)curNode為nextNode。直到curNode指向鏈表尾，即nextNode為空時(shí)，newList=curNode。結(jié)束~~

/* struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {} };*/ class Solution { public:ListNode* ReverseList(ListNode* pHead) {struct ListNode *newList;//反轉(zhuǎn)后的鏈表struct ListNode *curNode;//保存當(dāng)前結(jié)點(diǎn)struct ListNode *preNode;//保存上一個(gè)結(jié)點(diǎn)if(pHead==NULL)return NULL;newList=NULL;curNode=pHead;preNode=NULL;while(curNode!=NULL){struct ListNode *nextNode;nextNode=curNode->next;//保存下一個(gè)結(jié)點(diǎn)if(nextNode==NULL)//當(dāng)前指向鏈表的最后一個(gè)結(jié)點(diǎn){newList=curNode;}curNode->next=preNode;preNode=curNode;curNode=nextNode;}return newList;} };

題目描述

輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

解析：比較pHead1和pHead2的較小值賦給當(dāng)前結(jié)點(diǎn)，遞歸比較下一個(gè)較小值賦予下一個(gè)結(jié)點(diǎn)，直到某一鏈表為空

/* struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {} };*/ class Solution { public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){if( pHead1 == NULL )return pHead2;if( pHead2 == NULL )return pHead1;struct ListNode *newNode = NULL;if( pHead1->val < pHead2->val ){newNode = pHead1;newNode->next = Merge(pHead1->next,pHead2);}else{newNode = pHead2;newNode->next = Merge(pHead1,pHead2->next);}return newNode;} };
題目描述

輸入兩顆二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。

/* struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {} };*/ class Solution { public:bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){bool result = false;if( pRoot1 != NULL && pRoot2 != NULL ){if( pRoot1->val == pRoot2->val )result = DoesRootHaveSameLeaves(pRoot1,pRoot2);if( !result )result = HasSubtree(pRoot1->left,pRoot2);if( !result )result = HasSubtree(pRoot1->right,pRoot2);}return result;}bool DoesRootHaveSameLeaves(TreeNode* pRoot1, TreeNode* pRoot2){if( pRoot2 == NULL )return true;if( pRoot1 == NULL )return false;if( pRoot1->val != pRoot2->val )return false;return DoesRootHaveSameLeaves(pRoot1->left,pRoot2->left) && DoesRootHaveSameLeaves(pRoot1->right,pRoot2->right);} };

總結(jié)

以上是生活随笔為你收集整理的剑指offer 算法 （代码的鲁棒性）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。