划水总结剑指offer 链表系列1-USB迷|专注于互联网分享

划水总结剑指offer 链表系列1

最近在找实习，发现面试题和oj的题差距蛮大的，然后粗略的刷了一遍剑指offer.希望6月中旬前能拿个实习（捂脸哭）

1.首先总结关于链表的题.

（1）从尾到头打印一个链表.像我这样的憨憨上来就想这不是反向链表然后打印吗.此题并没有要翻转这个链表，而是可以递归的将链表的值倒序输出即可.

class Solution {
public:vector<int> ans;void diguiPrint(ListNode * p){if(!p)return;diguiPrint(p->next);ans.push_back(p->val);}vector<int> printListFromTailToHead(ListNode* head) {diguiPrint(head);return ans;}
};

接下来面试官大大说，你能不用递归吗？

然后我们用头插法做一个反向新链表

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:vector<int> ans;vector<int> printListFromTailToHead(ListNode* head) {if(!head) return ans;ListNode * newHead=new ListNode(0);ListNode * p=newHead;while(head){ListNode * temp=new ListNode(head->val);if(p->next)temp->next=p->next;p->next=temp;head=head->next;}p=p->next;while(p){ans.push_back(p->val);p=p->next;}return ans;}
};

然后hr小哥哥说，这也太麻烦了，再造一个链表属实憨憨.

最后我们考虑一下用栈存一下节点指针~

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:vector<int> ans;vector<int> printListFromTailToHead(ListNode* head) {stack<ListNode * >sta;while(head){sta.push(head);head=head->next;}while(!sta.empty()){ans.push_back(sta.top()->val);sta.pop();}return ans;}
};

(2)链表中的倒数第k个节点

HR哥哥说要求你最多走一遍链表.这时你想到了快慢指针，我整俩指针，一个比另一个先走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) {if(pListHead==NULL||k<=0)return NULL;ListNode * p1,*p2;p1=p2=pListHead;while(p1&&k){p1=p1->next;k--;}if(k==0){while(p1){p1=p1->next;p2=p2->next;}return p2;}return p1;}
};

这时候海哥小声嘀咕...我以前都是整个指针队列来解的.感觉这样更不容易错.再写一遍好咯..

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {if(pListHead==NULL||k<=0)return NULL;queue<ListNode *> que;while(pListHead){if(que.size()==k)que.pop();que.push(pListHead);pListHead=pListHead->next;}if(que.size()==k)return que.front();else return NULL;}
};

海哥你真是飞舞..连个实习都找不到，你这样怎么能得到五花肉的芳心？

那我再看几个题好了，下周还有面试机会，别骂了别骂了再骂人傻了.

（3）翻转链表

依稀记得以前应翔老师（曾经是最年轻（28）的副教授据说）说过，涉及到链表一定要考虑清楚，要是实在笨可以画图...应大佬好像去创业了....不知道有没有机会讨要一纸张offer...

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* ReverseList(ListNode* pHead) {ListNode* temp,*last;last=NULL;while(pHead){temp=pHead->next;pHead->next=last;last=pHead;pHead=temp;}return last;}
};

要个球.翻转个链表都能经常错.......应该用栈压进去然后取出来的时候更新next也能很简单的过吧....但是估计会被hr笑死....

(4)合并两个排序的链表....又因为返回的时候忘了返回的应该是创建的节点的下一个节点而错了....我完了我是飞舞

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){ListNode * p=new ListNode(0);ListNode * ans=p;while(pHead1&&pHead2){if(pHead1->val<=pHead2->val){ans->next=pHead1;pHead1=pHead1->next;}else{ans->next=pHead2;pHead2=pHead2->next;}ans=ans->next;}while(pHead1){ans->next=pHead1;ans=ans->next;pHead1=pHead1->next;}while(pHead2){ans->next=pHead2;ans=ans->next;pHead2=pHead2->next;}return p->next;}
};

（5）复杂链表的复制

这个题看起来好像没什么简单的解法？先常规，用个map/hashmap存一下旧节点和新节点的对应，然后第二次遍历的时候加random指针.

/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/
class Solution {
public:RandomListNode* Clone(RandomListNode* pHead){if(pHead==NULL)return pHead;RandomListNode * ans=new RandomListNode(0);RandomListNode * tempans=ans;RandomListNode * tempHead=pHead;map<RandomListNode*,RandomListNode*> m;while(tempHead){RandomListNode * temp=new RandomListNode(tempHead->label);m.insert(make_pair(tempHead,temp));tempans->next=temp;tempans=tempans->next;tempHead=tempHead->next;}tempans=ans;tempans=tempans->next;tempHead=pHead;while(tempHead){if(m.find(tempHead->random)!=m.end()){tempans->random=m.find(tempHead->random)->second;}tempans=tempans->next;tempHead=tempHead->next;}return ans->next;}
};

这时候hr小哥又说了，你能不用map吗？？？？？？？

这时候我一脸无奈，满足你的任性好了（逃，日常哭泣，到处都是bug）此时你想了想，如果是数组的话，复制就没这么麻烦了，不能挨个直接复制的原因是什么呢？当你到第k个节点的时候，random可能指向后面，所以你没办法这样创建，map也就是帮你把映射关系存下来最后加random指针而已，你完全可以遍历的时候直接在a后插入新的a，这样加random的映射就是a->random->next就是你要的random的复制出来的节点辣.....我是飞舞我没想出来.....（爆哭）

/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/
class Solution {
public:RandomListNode* Clone(RandomListNode* pHead){if(pHead==NULL)return NULL;RandomListNode * tempHead=pHead;while(tempHead){RandomListNode * tempNode=new RandomListNode(tempHead->label);tempNode->next=tempHead->next;tempHead->next=tempNode;tempHead=tempNode->next;}tempHead=pHead;while(tempHead){if(tempHead->random)tempHead->next->random=tempHead->random->next;tempHead=tempHead->next->next;}RandomListNode * ans=new RandomListNode(-1);RandomListNode * tempans=ans;tempHead=pHead;while(tempHead){tempans->next=tempHead->next;tempans=tempans->next;tempHead=tempHead->next->next;}pHead->next=NULL;return ans->next;}
};

这题有个超级恶心的坑.这题是怎么检测你是否直接返回了给你的指针？它竟然真的是直接拿自己的指针寻找有没有访问到你返回来的这些地址，QAQ我人傻了....知道了这个坑应该能很快写出来吧233

（6）二叉搜索树与双向链表

水题.写了递归，然后HR说，递归的本质是什么？（...我也不知道哇）.

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:TreeNode* Convert(TreeNode* pRootOfTree){if(pRootOfTree==NULL)return NULL;TreeNode * left=Convert(pRootOfTree->left);TreeNode * right=Convert(pRootOfTree->right);TreeNode * leftright=left;while(leftright&&leftright->right){leftright=leftright->right;}if(leftright)leftright->right=pRootOfTree;pRootOfTree->left=leftright;pRootOfTree->right=right;if(right)right->left=pRootOfTree;if(left)return left;return pRootOfTree;}
};