移除链表元素给你一个链表的头节点head和一个整数val请你删除链表中所有满足Node.val val的节点并返回新的头节点。输入head [1,2,6,3,4,5,6], val 6输出[1,2,3,4,5]该题就是就任让我们先构建一个删除和一个识别val 的数值来实现。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { if(headNULL) { return NULL; } struct ListNode* nodehead,*ptrhead-next; while(ptr ! NULL) { if(ptr-valval) { node-nextptr-next; free(ptr); ptrnode-next; } else { nodenode-next; ptrptr-next; } } if(head-valval) { ptrhead; headhead-next; free(ptr); ptrNULL; } return head; }解题思路1、判断是否为空指针如果为空指针就返回NULL2、声明一个节点指针和一个要被删除的预留指针。题目给的头指针不动便于后面要返回数值的时候可以之直接返回头指针。注意一定不要先从头指针入手从头指针的第二个元素进行操作头指针时应该链表的最重要的位置如果直接删除的head就会直接变成野指针返回时就会导致野指针的错误访问。3、构建循环体1判断条件ptr 到NULL就退出循环。2过程判断是否为val所要的数值否就正常移动位置4、判断头指针是否为对应数值。5、返回头指针。链表的中间节点快慢指针给你单链表的头结点head请你找出并返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。就如标题所说的利用快慢指针什么快慢指针呢就是字面意思应该指针走的块一个指针走的慢那如何用快慢指针解决问题呢例如在一个跑道上小明的速度为V小东的速度为2V那么在相同时间内小明总差小东的一半距离。所以这就是解题思路。声明两个指针一个指针每次走一步叫慢指针一个指针每次走两步叫快指针。当快指针到达空指针时慢指针的位置就刚好就是链表的中间位置。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { struct ListNode* v1,*v2;//快慢指针 v1v2head; while(v2!NULL) { if(v2-nextNULL)//防止访问野指针 v2v2-next; else { v2v2-next-next; v1v1-next; } } return v1; }返回倒数K个节点实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。注意本题相对原题稍作改动示例输入1-2-3-4-5 和k 2输出4这个题目偏简单计算总长度在对应位置结束就行。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ int kthToLast(struct ListNode* head, int k) { struct ListNode* phead; int count0; while(p) { pp-next; count; } while(count!k) { headhead-next; count--; } return head-val; }反转链表给你单链表的头节点head请你反转链表并返回反转后的链表。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { if(headNULL) { return NULL; } struct ListNode* lostNULL,*nodehead; headhead-next; while(head!NULL) { node-nextlost; lostnode; nodehead; headhead-next; } node-nextlost; return node; }解题思路1、先判断指针为NULL2、构建以左右中三节点因为有现成的head 的头指针就再多声明两个指针就可以lost node head三个其中lost NULLnodeheadheadhead-next 3、构建循环依次对应的指针交换方向。headNULL退出循环4、因为因为循环到最后还有lost 和node 两个节点还没有交换方向进行单独处理。5return node合并两个有序的链式表将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { //判断为空指针 if(list1NULL list2NULL) { return NULL; } else if(list1 !list2) { return list1; } else if(list2 !list1) { return list2; } //初始化 struct ListNode* headNULL,*pnodeNULL; //定节点和头节点 if(list1-val list2-val) { pnodelist1; list1list1-next; } else { pnodelist2; list2list2-next; } headpnode; pnode-nextNULL;//从新创出一条单链表但不用malloc的申请空间 while(list1 list2) { if(list1-val list2-val)//判断大小 { pnode-nextlist1; list1list1-next; } else { pnode-nextlist2; list2list2-next; } pnodepnode-next;//向前走 } if(list1)//漏下的节点 pnode-nextlist1; if(list2) pnode-nextlist2; return head; }解题思路我的思路不一定时最优解的因为两个指针交叉做的时候脑子有点过载了所以就用来一个最不容易解法就是单独再起一个链表当然可以用不到malloc 的申请空间就时把他们当成搭积木一样从两个链表里拆下一点拼接到新的链表里如果其中有一个链表已经被拆完了剩下的链表的接上去就可以。当然还有例外一种做法就是先通过比较头节点的大小选好要哪一个链表作为主链表选好主链表比较的第n和第n1个是不是在两数值之间的数值大小时就插入节点……到如果没有节点可以插入就退出如果主链表到头了就直接把剩下的节点加进去。相交链表给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回null。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ int count(struct ListNode** head) { if(*headNULL) { return 0; } return 1count(((*head)-next)); } struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { int Acount(headA),Bcount(headB); if(AB) { for(int i0;i(A-B);i) headAheadA-next; } else if(AB) { for(int i0;i(B-A);i) headBheadB-next; } while(headA!headB) { if(!headA || !headB) { return NULL; } headAheadA-next; headBheadB-next; } return headA; }解题思路计算两个链表的长度对齐长度向前走遇到相同地址就访问没有遇到就返回NULL重排链表给定一个单链表L的头节点head单链表L表示为L0 → L1 → … → Ln-1 → Ln请将其重新排列后变为L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middle_node(struct ListNode** head) { struct ListNode *v1, *v2, *cur; v1v2cur*head; while(v2-next!NULL v2-next-next ! NULL) { v1v1-next; v2v2-next-next; } curv1; v1v1-next; cur-nextNULL; return v1; } struct ListNode* fun(struct ListNode** head) { struct ListNode* nodenext,*lostnodeNULL; nodenext(*head)-next; while(nodenext!NULL) { (*head)-nextlostnode; lostnode*head; *headnodenext; nodenextnodenext-next; } (*head)-nextlostnode; return *head; } void reorderList(struct ListNode* head){ if(headNULL || head-nextNULL) return; struct ListNode* pheadhead; struct ListNode* midmiddle_node(phead); struct ListNode* retfun(mid),*nodeNULL; while(head ret) { nodehead; headhead-next; node-nextret; noderet; retret-next; node-nexthead; } return; }解题思路利用前面学到的算法找中间节点利用快慢指针反转链表并和两个链式表。环型链表给你一个链表的头节点head判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。注意pos不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环则返回true。 否则返回false。解题思路还是利用快慢指针因为快指针跑得快慢指针一定会被套圈遇到/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { if(head NULL || head-next NULL ) { return false; } struct ListNode* v1,*v2; v1v2head; while(v2 ! NULL v2-next ! NULL) { v1v1-next; v2v2-next-next; if(v1v2) { return true; } } return false; }变形给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。要求指针返回地址/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { if(head NULL || head-next NULL ) { return NULL; } struct ListNode* v1,*v2; v1v2head; while(v2 ! NULL v2-next ! NULL) { v1v1-next; v2v2-next-next; if(v1v2) { v2head; while(v1!v2) { v1v1-next; v2v2-next; } return v1; } } return NULL; }还是用刚才的代码进行改写。要只知道一个公式在一个完美的环的时候快指针和慢指针相遇到的时候位置一定时在起点位置非完美环的时候多余出来的位置就是在环的起点位置往后和快慢指针相遇的位置所以在相遇到后把快指针从链表的头指针开时与慢指针匀速前进就一定遇到位置和环的起点重合。感谢观看悠仁さん