目录
1.牛客网 CM11 链表分割
2.牛客网 OR36 链表的回文结构
3.LeetCode160. 相交链表
4.LeetCode 141. 环形链表
5.LeetCode 142. 环形链表 II
6.LeetCode 138. 复制带随机指针的链表
1.牛客网 CM11 链表分割
创建两个新链表，遍历原链表，依次将val小于x值的节点插入到链表一，其他的节点插入到链表2，最后将链表2连在链表1后面，返回链表一的首节点即可。
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
if (pHead==NULL)return NULL;
ListNode head1(0),head2(0),*tail1=&head1,*tail2=&head2,*p=pHead;
while(p){
if(p->valnext=p;
tail1=tail1->next;
p=p->next;
}else{
tail2->next=p;
tail2=tail2->next;
p=p->next;
}
}
tail1->next=head2.next;
tail2->next=NULL;
return head1.next;
}
};
2.牛客网 OR36 链表的回文结构
分三步求解，首先求链表的中间节点，然后反转中间节点以后的节点，最后判断回文结构。
第三步需要注意的是偶数个节点和奇数个节点的情况，奇数个节点判断条件是左右指针相等，而偶数时是左指针先走到了右指针的位置。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
if (A==NULL)return false;
ListNode*fast=A,*slow=A;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
}//求中间节点，即slow指针最后指向的位置
ListNode*cur=slow->next,*next,*pre=slow;
while(cur){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}//到此步，pre指针指向了反转后的头结点，1->2->2<-1<-pre
cur=A;//让cur指针从左往右走，pre从右往左走
while(cur->val==pre->val){
if(cur==pre)//奇数个节点情况
return true;
cur=cur->next;
if(cur==pre)//偶数个节点的情况
return true;
pre=pre->next;
}
return false;
}
3.LeetCode160. 相交链表
方法一：让两个指针分别从两个链表往后走，走到尾就从另一个链表头继续走，直到两指针相遇为止，每个指针分别遍历每个链表一次，若不相同则返回NULL。
方法二：让两个指针分别从两个链表往后走，计算两个链表的长度，，然后让两个链表从头走，先让长链表的指针走两链表的长度差，然后再一起走，若两链表相交则指针会在起始节点相遇，放回该节点。
//方法一
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if(!headA&&!headB)return NULL;
struct ListNode*p1=headA,*p2=headB;
while(p1&&p2){
if(p1==p2)return p1;
p1=p1->next;
p2=p2->next;
}
if(p1==NULL)p1=headB;
if(p2==NULL)p2=headA;
int count=1;//只让指针跳转一次，防止多次跳转
while(p1&&p2){
if(p1==p2)return p1;
p1=p1->next;
p2=p2->next;
if(p1==NULL&&count==1){
count=0;//只让指针跳转一次，防止多次跳转
p1=headB;
}
if(p2==NULL&&count==1){
count=0;//只让指针跳转一次，防止多次跳转
p2=headA;
}
}
return NULL;
}
4.LeetCode 141. 环形链表
运用快慢指针，让快指针一次走两步，慢指针一次走一步，只要有环就会在环中相遇，跳出循环返回true，否则快指针会先走到尾结点或尾结点后的NULL，返回false。
bool hasCycle(struct ListNode *head) {
if(head==NULL||head->next==NULL)return false;
struct ListNode*fast=head,*slow=NULL;
while(fast!=slow&&(fast!=NULL)&&fast->next!=NULL){
fast=fast->next->next;
if(slow==NULL)slow=head;
slow=slow->next;
}
return fast==slow;
}
5.LeetCode 142. 环形链表 II
同4，先判环，若有环，让快指针从头一次一步走，慢指针从相遇点一次一步走，两指针会在入环的第一个结点相遇，返回该节点。
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*slow=head;
struct ListNode*fast=head;
if(fast==NULL|| fast->next==NULL)return NULL;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
if(fast==slow){
fast=head;
while(fast!=slow){
slow=slow->next;
fast=fast->next;
}
return fast;
}
}
return NULL;
}
6.LeetCode 138. 复制带随机指针的链表
首先遍历链表并在每个节点后插入一个相同的节点，然后再遍历一次链表，让每个复制后的链表的随机指针指向复制前的随机指针的下一个结点，最后断开复制出结点与原链表的连接，形成新链表返回。
struct Node* copyRandomList(struct Node* head) {
if(head==NULL)return head;
struct Node*cur=head;
while(cur){
struct Node *NewNode=(struct Node*)malloc(sizeof(struct Node));
NewNode->val=cur->val;
NewNode->random=cur->random;
NewNode->next=cur->next;
cur->next=NewNode;
cur=NewNode->next;
}
cur=head->next;
while(cur){
if(cur->random)
cur->random = cur->random->next ;
cur=cur->next;
if(cur)cur=cur->next;
}
struct Node*newhead=head->next;
cur=head;
while(cur){
struct Node*next=cur->next;
cur->next=next->next;
if(next->next)next->next=cur->next->next;
cur=cur->next;
}
return newhead;
}
