牛客网剑指offer链表题目总结（共8道）
1、从尾到头打印链表（剑指3）
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
方法一：借助栈
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> ans;
if(head==NULL) return ans;
stack<ListNode*> s;
while(head!=NULL){
s.push(head);
head=head->next;
}
while(!s.empty()){
ans.push_back(s.top()->val);
s.pop();
}
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) {
ListNode *p=head;
if(p!=NULL){
if(p->next!=NULL){
printListFromTailToHead(p->next);
}
ans.push_back(p->val);
}
return ans;
}
};
2、链表中倒数第k个结点（剑指14）
快慢指针
/*
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 *quick=pListHead;
ListNode *slow=pListHead;
ListNode *head=pListHead;
int len=1;
while(head->next!=NULL){
head=head->next;
len++;
}
if(k>len) return NULL;
for(int i=1;i<k;i++)
{
if(quick->next!=NULL)
quick=quick->next;
}
while(quick->next!=NULL){
quick=quick->next;
slow=slow->next;
}
return slow;
}
};
3、反转链表（剑指15,同leetcode206）
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead==NULL||pHead->next==NULL) return pHead;
ListNode *head=ReverseList(pHead->next);
pHead->next->next=pHead;
pHead->next=NULL;
return head;
}
};
4、合并两个排序的链表（剑指16,同leetcode21）
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/*
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;
if(pHead1->val<pHead2->val){
pHead1->next=Merge(pHead1->next,pHead2);
return pHead1;
}
else{
pHead2->next=Merge(pHead1,pHead2->next);
return pHead2;
}
}
};
5、复杂链表的复制（剑指25）
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针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* curNode=pHead;
//复制每个节点，如：复制节点A得到A1，将A1插入节点A后面
while(curNode!=NULL){
RandomListNode* cloneNode=new RandomListNode(curNode->label);
RandomListNode* nextNode=curNode->next;
curNode->next=cloneNode;
cloneNode->next=nextNode;
curNode=nextNode;
}
//遍历链表，A1->random = A->random->next;
curNode=pHead;
while(curNode!=NULL){
curNode->next->random=curNode->random==NULL?NULL:curNode->random->next;
curNode=curNode->next->next;
}
//将链表拆分成原链表和复制后的链表
curNode=pHead;
RandomListNode* Head=pHead->next;
while(curNode!=NULL){
RandomListNode* cloneNode=curNode->next;
curNode->next=cloneNode->next;
cloneNode->next=cloneNode->next==NULL?NULL:cloneNode->next->next;
curNode=curNode->next;
}
return Head;
}
};
6、两个链表的第一个公共结点（剑指36,同leetcode160）
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
int len1=getLen(pHead1);
int len2=getLen(pHead2);
if(len1>len2) pHead1=goSteps(pHead1,len1-len2);
else pHead2=goSteps(pHead2,len2-len1);
while(pHead1!=NULL&&pHead2!=NULL){
if(pHead1->val==pHead2->val) return pHead1;
pHead1=pHead1->next;
pHead2=pHead2->next;
}
return pHead1;
}
ListNode * goSteps(ListNode *node,int k){
if(node==NULL||k<=0) return node;
while(k--){
node=node->next;
}
return node;
}
int getLen(ListNode * node){
if(node==NULL) return 0;
int len=1;
while(node->next!=NULL){
node=node->next;
len++;
}
return len;
}
};
7、链表中环的入口结点（剑指55,同leetcode142）
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode* quick=pHead;
ListNode* slow=pHead;
while(quick!=NULL&&quick->next!=NULL){
quick=quick->next->next;
slow=slow->next;
if(quick==slow) break;
}
if(quick==NULL||quick->next==NULL) return NULL;
ListNode* node=pHead;
while(node!=quick){
node=node->next;
quick=quick->next;
}
return node;
}
};
8、删除链表中重复的结点（剑指56）
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead==NULL||pHead->next==NULL) return pHead;
ListNode *node=pHead->next;
if(node->val==pHead->val){
while(node!=NULL&&node->val==pHead->val){
node=node->next;
}
return deleteDuplication(node);
}
else{
pHead->next=deleteDuplication(node);
return pHead;
}
}
};