1. 移除链表元素
题目描述
思路：
定义一个指针cur遍历整个链表，一个tail指针，cur遍历整个链表,如果cur->val!=val,就把tail的next存放cur指针指向的地址，这样下来，可以将链表中的!=val数据连接起来，tail指针作用就是起到连接作用，注意刚开始的时候如果第一个数据！=val,首先得将head,tail移动到cur指向的头结点上，为什么13行要将head=NULL;是为了防止空链表，如果链表最后一个元素==val的话，记得循环结束，将tail->next=NULL,当free掉最后一个6时，倒数第二个元素的next还保存6的地址，当free后，6地址上存的是随机值
代码：
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*cur=head; struct ListNode*tail=NULL; head=NULL;ya while(cur) { if(cur->val==val) {struct ListNode*del=cur; cur=cur->next; free(del); } else { if(tail==NULL) {tail=head=cur;} else {tail->next=cur; tail=tail->next; } cur=cur->next;} } if(tail) {tail->next=NULL;} return head; }
带图调试
2.反转链表
题目描述
思路1
逆序链表将存放下一个结点地址地址反过来，也就是2的next存1的地址，3的next存2的地址，4的next存3的地址，5的next存4的地址。你如果将2的next存1的地址，那么3的地址就会丢失，我们可以定义3个指针，一个指针指向前一个结点的地址，一个指针指向后一个结点指针，第三个结点n2为当前位置的指针，将n2->next存入n1,也就是在逆序链表，将每个指针都向后移动，继续修改下一个逆序方向，直到将图示中的箭头全部逆序完，n2指向空，当n3指向空后不再移动n3指针，此时n1指向的尾结点刚好是逆序之后的头结点，然后返回n1即可，如果是空链表的话，逆序之后也是空链表，直接return NULL;
代码
struct ListNode* reverseList(struct ListNode* head){ struct ListNode*n1=NULL; struct ListNode*n2= head; if(head==NULL) {return NULL;} struct ListNode*n3=n2->next; while(n2) {n2->next=n1; n1=n2; n2=n3; if(n3) {n3=n3->next;} } return n1; }
带图调试
思路2
定义一个cur指针遍历链表，当cur指向一个结点的时候，将该结点的next保存上一个结点的地址,然后将newnode指针移动到当前cur指针指向的位置，如果这样修改的话，会丢失掉下一个结点的地址，在使用一个指针x保存cur指针指向的结点的下一个结点的地址,cur指针移动到x指针指向的地址，进行下一次循环，第一个结点逆序成为最后一个结点，他的next=NULL;
代码
struct ListNode* reverseList(struct ListNode* head){ struct ListNode* cur=head; struct ListNode* newhead=NULL; while(cur) {struct ListNode*x=cur->next; cur->next=newhead; newhead=cur; cur=x; } return newhead; }
带图调试
>
3.链表的中间结点
题目描述
思路
定义一个快指针，一个慢指针，慢指针一次走一步，快指针一次走两步，结点为奇数个时，当慢指针走到一半时，快指针刚好指向尾结点，当结点数为偶数个时，当慢指针走到中间结点的第二个的时候，快指针走到尾结点的next;所以循环条件是fast和fast->next,如果有一个为NULL.循环结束。
代码
struct ListNode* middleNode(struct ListNode* head){ struct ListNode*slow=head; struct ListNode*fast=head; while(fast&&fast->next) {slow=slow->next; fast=fast->next->next; } return slow; }
带图调试
奇数个结点
偶数个结点
4.链表中倒数第k个结点
题目描述
思路
定义两个指针，都先指向头节点，先让fast指针走k步，然后每次fast指针走一步，slow指针走一步，当fast走到尾结点的下一个结点，slow指针刚好指向的是倒数第k个结点
代码
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode*fast= pListHead; struct ListNode*slow= pListHead; while(k) {if(fast==NULL)//防止fast大于链表长度 return fast; fast=fast->next; k--; } while(fast) {fast=fast->next; slow=slow->next; } return slow; }
带图调试，假设k等于2，
5.合并两个有序链表
题目描述
思路
定义一个哨兵位，定义两个指针，head和tail来先记录哨兵位的地址，然后比较list1指针指向的结点的val和list2指针指向结点的val,如果谁小，就将tail指针指向结点的next保存小的那个的地址，然后tail指针指向val小的那个结点，val小的对应的链表的指针list就指向该链表下一个结点，循环条件是list1&&list2都不为空的时候，当有一个链表被遍历完，直接把另一个链表剩下的部分的首结点地址存放在tail指针指向结点的next中，当两个链表都为空的时候，不进入循环，此时head->next=NULL,返回的就是空。
代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode*head; struct ListNode*tail; head=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); tail->next=NULL; while(list1&&list2) {if(list1->val<list2->val) { tail->next=list1; tail=tail->next; list1=list1->next; } else { tail->next=list2; tail=tail->next; list2=list2->next; } } if(list1) {tail->next=list1;} if(list2) {tail->next=list2;} return head->next; free(head); }
带图调试
6.链表分隔
题目描述
思路
先malloc两个哨兵位，一个作为小于x链表的头，一个作为大于等于x的头，定义4个指针，分别为greathead,greattail,lesshead,lesstail.这两个 greathead,greattail 先指向大于x的哨兵位，另外两个指向小于x的哨兵位。分别将哨兵位的next置为空，如果两个都为空链表的话就不进入循环，此时的lesshead->next==NULL;返回null.定义一个cur指针遍历链表，当cur指针指向空的话，分隔结束。
循环过程中，当cur->val<x,将lesstail指针指向的结点的next保存当前cur的地址，然后lesstail指针移动到cur指针指向的地址，然后cur移动到链表的下一个结点。当cur->val>=x,将greattail指针指向的结点的next保存当前cur指针指向结点的地址,然后greattail指针移动到当前cur指针指向的结点上，然后cur移动到链表的下一个结点，当循环结束，以greathead为哨兵位的链表都是大于等于x,以lesshead为哨兵位的链表是小于x,然后将lesstail->next=greathead->next;就是将两个小于x,和大于等于x的连接起来。但是最后那里为什么要将greattail->next=NULL;
当链表最后一个元素小于x的话，此时的结点数据为4的结点的next还保存着结点数据为2的地址，就会成为循环链表，所以必须将greattail->next=NULL;
代码
class Partition { public: ListNode* partition(ListNode* pHead, int x) { struct ListNode* greathead; struct ListNode* greattail; struct ListNode* lesshead; struct ListNode* lesstail; greathead=greattail=(struct ListNode* )malloc(sizeof(struct ListNode )); lesshead=lesstail=(struct ListNode* )malloc(sizeof(struct ListNode )); greattail->next=NULL; lesstail->next=NULL; struct ListNode* cur=pHead; while(cur) {if(cur->val<x) {lesstail->next=cur; lesstail=lesstail->next;} else {greattail->next=cur; greattail=greattail->next; } cur=cur->next; } lesstail->next=greathead->next; greattail->next=NULL; struct ListNode* list=lesshead->next; free(lesshead); free(greathead); return list; // write code here } };
带图调试
7.链表的回文结构
题目描述
思路
本题利用了之前求链表的中心结点和逆序链表的求解方法，先利用求链表的中心结点，用一个指针mid指向中心结点,再将mid指针指向结点以及后面的结点逆序，用rhead指针指向逆序新链表的头，然后遍历，如果head->val!=rhead->val，就直接return false,表示不相等，如果相等的话，让head指针和rhead指针指向下一个结点，等到rheadNULL,或者headNULL,循环没有在这之前return 掉，所以表示是回文结构return true。注意
head指针走红线，rhead指针走蓝线，要么rhead先指向NULL,要么read和head同时指向NULL
代码
class PalindromeList { public: struct ListNode* reverseList(struct ListNode* head) //逆序 { struct ListNode* n1 = NULL; struct ListNode* n2 = head; if (head == NULL) { return NULL; } struct ListNode* n3 = n2->next; while (n2) { n2->next = n1; n1 = n2; n2 = n3; if (n3) { n3 = n3->next; } } return n1; } struct ListNode* middleNode(struct ListNode* head) //找中心节点 { struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } bool chkPalindrome(ListNode* A)//回文结构判断 { struct ListNode* mid=middleNode(A); struct ListNode* rhead=reverseList(mid); struct ListNode* head=A; while(head&&rhead) {if(head->val!=rhead->val) {return false;} else {head=head->next; rhead=rhead->next; } } return true; } };
带图调试
8.相交链表
题目描述
思路
先判断两个链表是否有交点，然后在找交点的位置，定义两个指针分别指向两个链表的头结点cur1,cur2，如果cur1->next!=NULL,如此求出链表长度，当两个循环结束时，cur1和cur2都指向各自链表的尾结点，如果有相交，则尾结点的地址是一样的，也就是cur1=cur2,然后让longlist指针指向长的链表的头，shortlist指向短的链表的头，求出两个链表的长度差，然后让指向长链表的指针longlist先走长度差步，然后让longlist,shortlist同时走，当longlist==shortlist,该位置就是相交的位置。return longlist或者shortlist,当两个链表有一个为空链表，则一定不会有相交的位置直接返回NULL,
代码
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *cur1=headA; struct ListNode *cur2=headB; if(headA==NULL||headB==NULL) return NULL; int len1=1; int len2=1; while(cur1->next) {cur1=cur1->next; len1++; } while(cur2->next) {cur2=cur2->next; len2++; } if(cur1!=cur2) {return NULL; } struct ListNode* shortlist=headA; struct ListNode* longlist=headB; if(len1>len2) { shortlist=headB; longlist=headA;} int gap=abs(len1-len2); while(gap) {longlist=longlist->next; gap--; } while(shortlist!=longlist) {longlist=longlist->next; shortlist=shortlist->next; } return longlist; }
带图调试
9.环形链表
题目描述
思路
定义一个快指针fast一次走两步，定义一个慢指针slow一次走一步，如果为奇数个结点，无环的话，fast->next=NULL;如果为偶数结点的话，并且无环，fast=NULL,表示走完了整个链表，循环结束，如果有环的话循环不会结束，，当快指针走两步的时候，慢指针走一步，他们两个会指向同一块地址，所以当slow=fast,直接return true.如果没环，循环到fast=NULL,或者fast->next=NULL;
循环结束，return false
代码
bool hasCycle(struct ListNode *head) { struct ListNode* slow=head; struct ListNode* fast=head; while(fast&&fast->next) {slow=slow->next; fast=fast->next->next; if(slow==fast) { return true; } } return false; }
带图调试
10.环形链表2
题目描述
思路
根据上一题的思路，找出fast,slow相遇的结点，然后用新的指针meet指向这个相遇的结点，然后head指针走一步，meet指针走一步，当两个指针相遇的时候就是刚进环的结点的地址
代码
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast=head; struct ListNode* slow=head; while(fast&&fast->next) {fast=fast->next->next; slow=slow->next; if(fast==slow) { struct ListNode* meet=slow; while(meet!=head) {head=head->next; meet=meet->next; } return head; } } return NULL; }
带图调试
