练习题1移除链表元素
要考虑的情况
如果只有一个节点，且这个节点要删除，则返回NULL
struct ListNode* removeElements(struct ListNode* head, int val){ while(head != NULL && head->val == val){ head = head->next; } struct ListNode* fast = head; struct ListNode* slow =head; struct ListNode* slow1 =head; if (head ==NULL) return NULL;//如果头节点为空，则直接返回 while (fast!= NULL) { while (fast->val!=val) { slow = fast; if (slow->next == NULL) return head;//如果遍历完整个链表，fast为NULL，都没找到val，则直接返回 fast = fast->next; } if (fast->val == val) { slow->next = fast->next; fast = fast->next;//跨过要删除的节点 } } if (slow1->val==val)//如果只有一个节点，且这个节点要删除，则返回空 return NULL; return head; }
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur=head; struct ListNode* prve=NULL; while(cur) { if(cur->val==val) { if(cur==head) { head=head->next; free(cur); cur=head; } else { prve->next=cur->next; free(cur); cur=prve->next; } } else { prve=cur; cur=cur->next; } } return head; }
还可以把 非valu的节点，插到新链表
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur=head; struct ListNode* tail=NULL; struct ListNode* newhead=NULL; while(cur) { if(cur->val!=val) { if(tail==NULL) { tail=newhead=cur; } else { tail->next=cur; tail=tail->next; } cur=cur->next; } else { struct ListNode* del=cur; cur=cur->next; free(del); } } if(tail) tail->next=NULL; return newhead; }
带哨兵头
head不存储有效数据
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* guard=(struct ListNode* )malloc(sizeof(struct ListNode)); struct ListNode*tail=guard; struct ListNode*cur=head; while(cur) { if(cur->val!=val) { tail->next=cur; tail=tail->next; cur=cur->next; } else { struct ListNode* del=cur; cur=cur->next; free(del); } } if(tail) tail->next=NULL; return guard->next; }
带哨兵位的头节点，传参的时候不需要传二级指针
替代之前的二级指针：
1.返回新链表头
2.设计为带哨兵位
单链表：
1.实际运用中很少带头
2.OJ题基本不带头
练习题2合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode*newhead=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode*tail=newhead; while(list1!=NULL&&list2!=NULL) { if(list1->val>list2->val) { newhead->next=list2;//newhead与第小的数链接 list2=list2->next;//遍历下一个数 } else { newhead->next=list1; list1=list1->next; } newhead=newhead->next;//newhead往下走，要存下一个数 } while(list1!=NULL) { newhead->next=list1; list1=list1->next; newhead=newhead->next; } while(list2!=NULL) { newhead->next=list2; list2=list2->next; newhead=newhead->next; } newhead->next=NULL; return tail->next; }
练习题3反转链表
struct ListNode* reverseList(struct ListNode* head){ struct ListNode*cur=head; struct ListNode*next=NULL; struct ListNode*newhead=NULL; while(cur) { next=cur->next; cur->next=newhead; newhead=cur; cur=next; } return newhead; }
方法二：反转链表
struct ListNode* reverseList(struct ListNode* head){ struct ListNode*cur=head; struct ListNode*prve=NULL; while(cur) { struct ListNode*t=cur->next; cur->next=prve; prve=cur; cur=t; } return prve; }
习题4 链表的中间节点
struct ListNode* middleNode(struct ListNode* head){ struct ListNode*fast,* slow; fast=slow=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; } return slow; }
采用快慢指针：快指针一次走俩步，慢指针走一步
习题5 倒数第K个节点
采用快慢指针法
方法一：fast先走k步，然后slow和fast一块一步一步走，等fast位空，则停止前进，slow所在位置就是倒数第k个
这里k=4，则slow要等于倒数第四个
fast为空，找到了
方法二：fast先走k-1补，然后slow和fast一起一步一步走，等fast->next=NULL，则找到了
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast=pListHead; struct ListNode *slow=pListHead; if(pListHead==NULL) return NULL; while(k--) { if(fast) fast=fast->next; else return NULL; } while(fast) { slow=slow->next; fast=fast->next; } return slow; }
