服务网站设计案例,万网域名注册商,搭建网站 在线浏览功能,wordpress 2.0 下载目录
1.反转链表
反转链表总结#xff1a;
2.链表的中间节点#xff08;快慢指针法#xff09;
快慢指针法总结 1.反转链表 在这道题中#xff0c;我们需要把一个单链表反转它们的指向#xff0c;这里#xff0c;我们给出了一个好理解的简单解法#xff0c;就是用三…目录
1.反转链表
反转链表总结
2.链表的中间节点快慢指针法
快慢指针法总结 1.反转链表 在这道题中我们需要把一个单链表反转它们的指向这里我们给出了一个好理解的简单解法就是用三个指针去解决这道题。 先给出完整的代码。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {//创建头指针ListNode* n1 NULL;ListNode* n2 head;if(n2NULL){return NULL;}ListNode* n3 n2-next;while(n2){n2-nextn1;n1 n2;n2 n3;if(n3)n3n3-next;}return n1;
}
假设我们的原链表为head我们申请了n1n2n3三个指针其中n1初始化为NULLn2初始化为head图中的第一个节点n3初始化为head-next也就是图中的第二个节点 第一次操作 第二次操作 第三次操作 第四次操作注意最后一次操作n3的指针指向不能让n3出现NULL-NULL的情况 然后我们的步骤如下 1、遍历原链表中的每个节点每次遍历先使n1的指针指向n2的节点n1n2然后让n2的节点指向n3n2n3最后让n3的节点指向n3的下一个节点n3n3-next 2、注意要在循环中判断以下n3的指针指向防止出现NULL-NULL的情况。 反转链表总结
这里面最重要的是我们要改变当前的节点的指向关系的时候注意要先把当前节点指向的下一个节点的指针保存下来。如果我们不保存就改变指向关系的化就会导致一个严重的错误我们原链表中当前节点的下一个节点就找不到了。如下图当我们遍历原链表的时候我们需要让第一个链表的节点指向NULL但是我们没有存储第二个节点的地址当我们改变了指向让第一个节点的地址为NULL的时候原链表后面的节点就没办法找到。 这个时候我们就需要在改变当前节点指向关系前将这个节点的next域存储起来这样我们就可以实现通过n3找到原链表节点通过n2就可以改变当前链表的指向关系。 2.链表的中间节点快慢指针法 1在看到这个题的时候我们能够都想到的同用解法是用计数器来做 下面是具体步骤: 1、首先我们遍历原链表定义一个变量count存储节点的个数然后将每个节点都做1的操作这样我们就得到了链表的节点总个数count。 2、然后我们对count/2得到中间节点的位置然后再次遍历原链表找到下标为count/2的位置上的节点并返回。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* pcur head;int count 0;while(pcur){count;pcur pcur-next;}pcur head;count / 2;while(count--){pcur pcur-next;}return pcur;
} 2这里提供一种很巧妙的解题方法我们只需要遍历一遍链表就能够得到链表中间的位置这个就是我们接下来介绍的快慢指针法了。
先给出代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {if(headNULL){return NULL;}//定义快慢指针ListNode* slow ,*fast; slow fast head;while(fast fast-next){slow slow-next;fast fast-next-next;}return slow;
} 1、刚开始我们创建两个指针slow和fast都指向头节点. 2、接下来我们规定slow每次走一个节点fast每次走两个节点当遍历结束时slow指针指向的节点就是我们需要的中间节点。 3、循环结束的条件fast!NULL fast-next!NULL。 我们继续深入解析以下结束的循环条件是如何得到的这就得要根据节点个数是否为奇数和偶数来确定。
1当讨论的节点个数为偶数的时候:
阶段1 阶段2 阶段3 从这里可以得到当我们得fast指针指向NULL时循环结束此时slow指向得节点正好是我们需要得中间节点。
2当讨论的节点个数为奇数的时候:
阶段1 阶段2 阶段3 从这里我们可以看出来当fast的next指向为NULL时我们的循环结束此时slow指针指向的节点就是我们的中间节点。 然后我们得出结论当fast和fast-next有一个为NULL时我们的循环条件就结束此时我们的slow指针指向的节点就是中间节点。 这里的 快慢指针法总结
这里的快慢指针法可以很快的找到我们所需要的单链表中的中间节点代码量也很少是一个很不错的解题思路在涉及到用中间节点解题的时候可以参考以下这个方法。
