链表

一、从尾到头打印链表

题目：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

解题思路：使用栈作为中转，可以实现倒置打印

classSolution {
public:vector<int> printListFromTailToHead(ListNode* head){//使用栈完成中转stack<int>s;vector<int>ArrayList;ListNode *p=head; //遍历指针while(p!=NULL){s.push(p->val); //入栈p=p->next;}//出栈int len=s.size();for(int i=0;i<len;i++){ArrayList.push_back(s.top());s.pop();}return ArrayList;}
};

二、链表中倒数第k个结点

题目描述：输入一个链表，输出该链表中倒数第k个结点。

解答思路：使用快慢指针。第一个指针先走k步，第二个指针再和第一个指针一起走，当第一个指针遍历到尾部时，第二个指针也就遍历到了第k个结点位置了。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/classSolution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsignedint k){if(pListHead==NULL||k==0)returnNULL;ListNode* first=pListHead;ListNode* second=NULL;if(k==0)returnNULL;for(int j=0;j<k-1;++j){if(first->next!=NULL)first=first->next;elsereturnNULL;}second=pListHead;while(first->next!=NULL){first=first->next;second=second->next;}return second;}
};

三、孩子们的游戏（圆圈中最后剩下的数字）

题目描述：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

解题思路一：使用std::list来模拟一个环形链表。既然是链表，那么需要注意的就犹豫一下几点：

• 环形结构，首尾相连

• 删除当前节点时需要先保存后面的节点，保证不断链

这种方法的时间复杂度为

编辑，空间复杂度为

编辑。

classSolution {
public:intLastRemaining_Solution(int n, int m){if(n==0||m==0) return-1;list<int>numbers; //定义list模拟环形链表for(int i=0;i<n;i++) //将元素添加到list中numbers.push_back(i);list<int>::iterator current=numbers.begin(); //定义迭代器while(numbers.size()>1){//遍历第m个小朋友for(int j=1;j<m;j++){++current;if(current==numbers.end()) current=numbers.begin(); //模仿环的结构}list<int>::iterator next=++current; //用来保存后面的节点if(next==numbers.end()) next=numbers.begin(); //模仿环的结构current--;numbers.erase(current); //删除第m个小朋友current=next;}return *(current);}
};

解题思路二：使用递归公式进行计算。

编辑

classSolution {
public:intLastRemaining_Solution(int n, int m){if(n==0||m==0) return-1;int last=0;for(int i=2;i<=n;i++)last=(last+m)%i;return last;}
};

四、两个链表的第一个公共结点

题目描述：输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

解题思路：先计算两个链表相差的部分，长的多走几步，等二者同步之后，再共同遍历。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/classSolution {
public:intGetLength(ListNode* p){int len=0;ListNode* look=p;while(look!=nullptr){look=look->next;len++;}return len;}ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2){int len1=GetLength(pHead1);int len2=GetLength(pHead2);int gap=0;if(len1>len2){gap=len1-len2;for(int i=0;i<gap;i++){pHead1=pHead1->next;}}elseif(len1<len2){gap=len2-len1;for(int j=0;j<gap;j++){pHead2=pHead2->next;}}while(pHead1!=pHead2&&pHead1->val!=pHead2->val){pHead1=pHead1->next; pHead2=pHead2->next;}ListNode* pCommon=pHead1;return pCommon;}
};