单链表进阶题目，点进来看一下这些题你都会吗
单链表进阶题目，点进来看一下这些题你都会吗
前言：
前面我们已经讲解了关于单链表，双链表以及一些相关的简单的题，本次我们就要上升一些难度，给大家带来一些更加有难度的题目。
题目一：OR36 链表的回文结构
本题链接：链表的回文结构_牛客题霸_牛客网
虽然我将这个题放在了第一个，但是这是本次几道题中难度最大的一个，下面我们来看一下这个题的题意吧。
这个题的意思很容易就能搞明白，就是判断一个链表是不是一个回文链表，但是真的当我们下手去写代码的时候就能发现这个题并不是那么的简单，因为这个题给的是一个链表，链表不像数组，我们只能通过一个节点去访问下一个节点，而且是单向的，所以我们怎样才能处理好这个问题呢。
这里我来给大家说一下我的思路吧：
我的思路是这样的，分为三个步骤：
- 首先我们用一个函数得到链表的中间节点
- 然后我们将中间节点后面的节点全部逆置
- 最后我们将这两个链表的进行比较
下面我们就来看一下我的实现代码：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
struct ListNode*middleNode(struct ListNode*head)
{
ListNode*slow=head,*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
struct ListNode*reverlist(struct ListNode*head)
{
struct ListNode*cur=head;
struct ListNode*newhead=NULL;
while(cur)
{
struct ListNode*next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}
bool chkPalindrome(ListNode* A)
{
struct ListNode* mid=middleNode(A);
struct ListNode* rmid=reverlist(mid);
while(rmid&&A)
{
if(rmid->val!=A->val)return false;
rmid=rmid->next;
A=A->next;
}
return true;
}
};题目二：返回倒数第 k 个节点
我们下来看一下题目：
这个题相对于上面那个还是要简单不少的，我们来说一下这个题的思路：
大致思路就是我们用一个双指针，让快指针先走上k个节点，那样我们的慢指针和快指针就始终差k个节点了，往后我们再进行循环，每次两个指针都走一步。
思路很简单，下面我们来看一下代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
typedef struct ListNode ListNode;
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode*slow=head,*fast=head;
while(k--)
{
fast=fast->next;
}
while(fast!=NULL)
{
slow=slow->next;
fast=fast->next;
}
return slow->val;
}
};题目三：相交链表
我们再来看一下最后一道题，这个题的大致思路是要求我们判断两个代码是不是相交链表，所谓相交链表，并不是说像这样：
中间有一个相同的就可以，当然链表也不会出现这种情况，因为这样的链表的红色节点就指向了两个节点了。
所以题目的要求应该是这样的：
下面我们就来说一下这个题的思路：
首先我们应该先判断一下这个代码是不是相交代码，如果是，那么起码有一个节点是相同的，那么也就是最后一个节点，这里我们就得到最后一个节点，最后判断一下即可。 然后如果是，我们就要在得到最后一个节点的同时记录一下链表的长度，因为我们接下来的思路是先对长一点的链表进行操作，操作到其剩下的节点和另一个链表一样长之后，我们就一一比较就可以了，只要有一个相等，那么我们就可以结束循环了
下面我们来看一下代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
typedef struct ListNode ListNode;
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode*cur1=headA,*cur2=headB;
int count1=1,count2=1;
while(cur1->next)
{
cur1=cur1->next;
count1++;
}
while(cur2->next)
{
cur2=cur2->next;
count2++;
}
if(cur1!=cur2)return NULL;
ListNode*longlist=headA,*shortlist=headB;
int len=abs(count1-count2);
if(count1<count2)
{
longlist=headB;
shortlist=headA;
}
while(len--)
{
longlist=longlist->next;
}
while(longlist!=shortlist)
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return longlist;
}
};