剑指offer 算法 （代码的鲁棒性）

题目描述

输入一个链表，输出该链表中倒数第k个结点。

解析：p1,p2保持k-1的距离，当p1指向链表尾时，p2正好指向倒数第k个结点

/* 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的距离，当p1指向链表尾时，p2正好指向倒数第k个结点if( pListHead==NULL || k==0 )//空链表 返回NULL； k从1开始计数 k=0时返回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超过链表长度return NULL;}while(p1->next!=NULL){p1=p1->next;p2=p2->next;}return p2;} };

题目描述

输入一个链表，反转链表后，输出链表的所有元素。

解析：curNode保存当前结点，preNode保存已遍历过的反转好的链表的头结点，newList作最后反转好的链表头。当curNode不是指向链表尾时，先保存链表nextNode值，使curNode->next指向preNode，preNode再保存curNode，最后恢复curNode为nextNode。直到curNode指向链表尾，即nextNode为空时，newList=curNode。结束~~

/* struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {} };*/ class Solution { public:ListNode* ReverseList(ListNode* pHead) {struct ListNode *newList;//反转后的链表struct ListNode *curNode;//保存当前结点struct ListNode *preNode;//保存上一个结点if(pHead==NULL)return NULL;newList=NULL;curNode=pHead;preNode=NULL;while(curNode!=NULL){struct ListNode *nextNode;nextNode=curNode->next;//保存下一个结点if(nextNode==NULL)//当前指向链表的最后一个结点{newList=curNode;}curNode->next=preNode;preNode=curNode;curNode=nextNode;}return newList;} };

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解析：比较pHead1和pHead2的较小值赋给当前结点，递归比较下一个较小值赋予下一个结点，直到某一链表为空

/* 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的子结构。

/* 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);} };

总结

以上是生活随笔为你收集整理的剑指offer 算法 （代码的鲁棒性）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。