反转链表
解题思路
指针反转法
这里我们直接把节点的指针进行反转就行，反转的时候要注意保存好下一个节点的地址和上一个节点的地址。
n1表示当前节点的上一个节点的地址
n2表示当前节点
n3表示当期节点的下一个节点的地址
节点插入法
我们创建新的头节点的地址，原链表中的每个节点一个一个进行头插。
代码
指针反转法
struct ListNode* reverseList(struct ListNode* head){ if(head==NULL) return head; struct ListNode* n1,*n2,*n3; n1=NULL; n2=head; n3=head->next; while(n3) { n2->next=n1; n1=n2; n2=n3; n3=n2->next; } n2->next=n1; return n2; }
节点插入法
struct ListNode* reverseList(struct ListNode* head){ struct ListNode* newhead=NULL; while(head) { struct ListNode* cur=head; head=head->next; cur->next=newhead; newhead=cur; } return newhead; }
链表的中间结点
解题思路
快慢指针法，慢指针走一步，快指针走两步。当快指针指向为空的时候。慢指针指向的节点即为中间的节点。
代码
struct ListNode* middleNode(struct ListNode* head){ struct ListNode *low,*quick; low=head; quick=head; while(quick->next) { low=low->next; quick=quick->next; if(quick==NULL) break; quick=quick->next; if(quick==NULL) break; } return low; }
移除链表元素
解题思路
方法1：遍历链表，遇到val，则跳过该节点。
代码
方法1：
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur=head; struct ListNode* curpro=head; while(head&&head->val==val) { head=head->next; free(cur); cur=head; } while(cur) { if(cur->val==val) { curpro->next=cur->next; free(cur); cur=curpro->next; } else{ curpro=cur; cur=curpro->next; } } return head; }
链表中倒数第k个结点
解题思路
快慢指针法，先让快指针走k步，然后快慢指针一起走。直到快指针为空的时候，慢指针指向的节点就是倒数第k个节点。
注意k的值大于节点个数的时候，返回的为空。
代码
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode *slow,*quick; slow=NULL; quick=pListHead; int i=0; while(i<k&&quick) { quick=quick->next; i++; } if(i==k) { slow=pListHead; while(quick) { slow=slow->next; quick=quick->next; } } return slow; }
合并两个有序链表
解题思路
开辟一个头节点用于当中新的链表，里面不存有效值，对应给的两个链表，从首个节点开始进行val值的比较，小的那个值的节点插入到新的节点的后面，一直到某个链表节点的结尾。把剩下一个链表的全部插入到新链表的后面。最后不要忘记释放头节点。
代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur=newhead; while(list1&&list2) { if(list1->val<list2->val) { cur->next=list1; list1=list1->next; cur=cur->next; } else { cur->next=list2; list2=list2->next; cur=cur->next; } } if(list1==NULL) { cur->next=list2; } else{ cur->next=list1; } //销毁 cur=newhead->next; free(newhead); newhead=NULL; return cur; }
链表分割
题目的意思是这样的,小于x的节点在前面，大于等于x的节点排在后面，其相对位置不变。看下面的更能更好的理解。
解题思路
我们把原链表分成2个链表，第一个链表为小于x的链表，第二个链表为大于等于x的链表。最后第二个链表连接到第一个链表的后面。返回第一个链表的地址。
形成两个链表的过程中，遍历原链表。两个链表都是带头节点的。
代码
class Partition { public: ListNode* partition(ListNode* pHead, int x) { struct ListNode *list1=(struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *list2=(struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *head1,*head2,*tail1,*tail2; list1->next=NULL; list2->next=NULL; head1=tail1=list1; head2=tail2=list2; while(pHead) { if(pHead->val<x) { tail1->next=pHead; pHead=pHead->next; tail1=tail1->next; } else { tail2->next=pHead; pHead=pHead->next; tail2=tail2->next; } } tail2->next=NULL; tail1->next=head2->next; struct ListNode *head=head1->next; free(list1); free(list2); return head; } };
另一种写法
class Partition { public: ListNode* partition(ListNode* pHead, int x) { struct ListNode *head1,*head2,*tail1,*tail2; head1=tail1=head2=tail2=NULL; while(pHead) { if(pHead->val<x) { if(tail1==NULL) { head1=tail1=pHead; } else { tail1->next=pHead; tail1=tail1->next; } } else { if(tail2==NULL) { head2=tail2=pHead; } else { tail2->next=pHead; tail2=tail2->next; } } pHead=pHead->next; } if (head1 == NULL) return head2; if (head2 == NULL) return head1; tail2->next=NULL; tail1->next=head2; struct ListNode *head=head1; return head; } };
链表的回文结构
解题思路
1.找到中间节点，然后把中间节点后面的节点进行逆序
2.没有逆序的部分与逆序的部分进行比较，相同即为回文，否则不是回文。
3.是回文结束的标准为节点为空。
4.恢复破坏的链表结构
代码
struct ListNode* middleNode(struct ListNode* head) { struct ListNode *slow,*quick; slow=quick=head; while(head&&head->next) { slow=slow->next; head=head->next->next; } return slow; } struct ListNode* reverseList(struct ListNode* head) { if(head==NULL) return NULL; struct ListNode *n1,*n2,*n3; n1=NULL; n2=head; n3=head->next; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3) n3=n3->next; } struct ListNode* newhead=n1; return newhead; } bool isPalindrome(struct ListNode* head){ struct ListNode* mid= middleNode(head); mid=reverseList(mid); struct ListNode* temp=mid; struct ListNode* cur=head; while(cur&&mid) { if(cur->val!=mid->val) { reverseList(temp); return false; } else { cur=cur->next; mid=mid->next; } } reverseList(temp); return true; }
相交链表
解题思路
1.先求出两个链表的长度，求出它们的差值。
2.让长的链表先走差值步。
3.然后两人链表同时走，发现有地址相同的时候就返回该地址的节点。没有就返回空。
代码
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *curA=headA,*curB=headB; int lenA=0,lenB=0; while(curA) { curA=curA->next; lenA++; } while(curB) { curB=curB->next; lenB++; } struct ListNode *shorts=headA,*longs=headB; if(lenA>lenB) { shorts=headB; longs=headA; } int k=lenA>lenB?lenA-lenB:lenB-lenA; while(k--) { longs=longs->next; } while(shorts&&longs) { if(shorts==longs) return shorts; else { shorts=shorts->next; longs=longs->next; } } return NULL; }
环形链表1
解题思路
本题用快慢指针进行解决，快指针走2步，慢指针走一步。当两个指针相等时即存在环。
代码
bool hasCycle(struct ListNode *head) { struct ListNode *slow,*quick; slow=quick=head; while(quick&&quick->next) { slow=slow->next; quick=quick->next->next; if(slow==quick) return true; } return false; }
环形链表2
解题思路
思路1：
先用快慢指针找到他俩相遇的节点，然后一个从头开始走，一个从相遇点开始走，当它们相遇的时候即为环的第一个节点。
证明
假设不是环的长度为L，环的长度为C。这里L表达节点的个数。
快指针一次走两步，慢指针一次走一步，当慢指针开始进入环的时候，快指针走了L+N*C+Y（N表示整数，Y表示不足1圈的步数），慢指针走了L。
这时，慢指针和快指针开始了追击。当快，慢指针相遇的时候。假设慢指针在环中走了X步，快指针走了C-Y+X步。
慢指针：L+X
快指针：L+(N+1) * C+X
由快慢指针的关系：
2(L+X)=L+(N+1) * C+X =>L=(N+1)*C-X=> L=N * C+(C-X)
L=N * C+(C-X)
从这个表达式中可以看出来一个指针从头开始走，另一个从相遇点开始走，相遇时就是环的第一个节点。
思路2：
同样需要快慢指针，当快慢指针相遇的时候，把该节点制成空。这时题目就变成找两个链表的相交节点。注意： 最后要把破坏的链表恢复到原来的模样。
代码
思路1：
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow,*quick; slow=quick=head; while(quick&&quick->next) { slow=slow->next; quick=quick->next->next; if(slow==quick) { struct ListNode* cur=head; while(cur!=slow) { cur=cur->next; slow=slow->next; } return cur; } } return NULL; }
思路2：
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow,*quick; int L1,L2; L1=L2=0; slow=quick=head; while(quick&&quick->next) { slow=slow->next; quick=quick->next->next; if(slow==quick) { struct ListNode*cur=head; struct ListNode* newhead=slow->next; slow=slow->next; quick->next=NULL; while(cur) { cur=cur->next; L1++; } while(slow) { slow=slow->next; L2++; } int divalue=L1>L2?L1-L2:L2-L1; struct ListNode *shorts=head,*longs=newhead; if(L1>L2) { shorts=newhead; longs=head; } while(divalue--) longs=longs->next; while(shorts!=longs) { shorts=shorts->next; longs=longs->next; } quick->next=newhead; return shorts; } } return NULL; }
复制带随机指针的链表
解题思路
1.原链表每个节点后面插入一个和它一样的节点。
新的链表就是插入的节点（还没有链接在一起）
2.复制节点中random指向的节点 == 原节点中random指向的节点的后一个节点。从上图中可以看出来。
3.恢复原链表，剪除新链表。
先让原链表中的节点指向新链表节点的下一个节点，原链表节点移动一位。
然后新链表中的节点指向原链表节点的下一个节点。一次遍历就行。
代码
struct Node* copyRandomList(struct Node* head) { struct Node* cur=head; while(cur) { struct Node *newnode=(struct Node*)malloc(sizeof(struct Node)); newnode->val=cur->val; //插进去 newnode->next=cur->next; cur->next=newnode; cur=newnode->next; } //random 指向恢复 cur=head; while(cur) { struct Node* curnext=cur->next; if(cur->random==NULL) curnext->random=NULL; else curnext->random=cur->random->next; cur=curnext->next; } //恢复原链表，新成新链表 cur=head; struct Node *newhead=NULL,*newtail=NULL; while(cur) { if(newtail==NULL) newhead=newtail=cur->next; cur->next=newtail->next; cur=cur->next; if(cur) newtail->next=cur->next; newtail=newtail->next; } return newhead; }
