1.返回倒数第k个节点

OJ链接

思路

有点像高中学的相对位移
利用快慢指针，开始时都指向头节点，然后让快指针先走k步，再让两个指针同时走，直到快指针走到 NULL ,返回慢指针的数据就行

解析

typedef struct ListNode lsnode;
int kthToLast(struct ListNode* head, int k){lsnode* slow=head,*fast=head;while(k--){fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow->val;
}

2.链表的回文结构​

OJ链接

思路

回文的意思就是轴对称，也就是里面的数据呈轴对称就是会文结构

解析1（空间复杂度不符合）

可以把链表里的数据全放到数组中，然后判断数组是否是回文就行

 bool chkPalindrome(ListNode* A) {// write code here//if(A==NULL)//return NULL;int arr[900];int i=0;ListNode*purc=A;while(purc){arr[i++]=purc->val;           purc=purc->next;}      int left=0;int right=i-1;while(left<right){if(arr[left++]!=arr[right--]){return false;}}return true;}

解析2

按部就班的判断链表是否是回文结构
那么就要先找链表的中间节点，然后从中间节点把链表分为两部分，把后部分逆置和前部分进行比较就行

 ListNode* midnode(ListNode*head){ListNode* slow=head;ListNode* fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;}return slow;}ListNode*nizhi(ListNode*head){ListNode*l1=nullptr,*l2=head,*l3=head->next;while(l2){l2->next=l1;     l1=l2;         l2=l3;if(l3)l3=l3->next;}return l1;}bool chkPalindrome(ListNode* A) {// write code here     //先找中间节点ListNode*phead=A;ListNode* mid = midnode (phead);//然后逆置第二部分ListNode* newhead=nizhi(mid);//然后比较，直到两个有一个为空while(A && newhead){if(A->val != newhead->val)return false;else{ A=A->next;newhead = newhead->next;}}return true;}

3.相交链表​

OJ链接

思路

先把两个链表长度对齐，然后同步遍历

解析

typedef struct ListNode lsnode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{lsnode*l1=headA,*l2=headB;int sizea=0;int sizeb=0;while(l1){sizea++;l1=l1->next;      }while(l2){sizeb++;l2=l2->next;     }//计算a和b的长度，让长的先走差值步，到同一起点上int gap=abs(sizea-sizeb);if(sizea < sizeb){lsnode*plong= headB;lsnode*pshort=headA;}lsnode* plong = headA;lsnode* pshort = headB;while(gap--){plong=plong->next;}//开始比较while(plong && pshort){//这里比较地址，如果比较值得话有问题if(plong == pshort){ return pshort;}plong=plong->next;pshort=pshort->next;    }return NULL;   
}