昆明做网站建设价位,鼓楼福州网站建设,茶山网站建设,个人搭建网站要多少钱前言#x1f308;前段时间我们学习了单向链表和双向链表#xff0c;本期将带来3道与链表相关的OJ题来巩固对链表的理解。话不多说#xff0c;让我们进入今天的题目吧#xff01;#x1f680;本期的题目有#xff1a;反转单链表、链表的中间结点、合并两个有序链表反转单链…前言前段时间我们学习了单向链表和双向链表本期将带来3道与链表相关的OJ题来巩固对链表的理解。话不多说让我们进入今天的题目吧本期的题目有反转单链表、链表的中间结点、合并两个有序链表反转单链表✨a.题目b.题解分析(迭代)三指针法:我们可以直接在原链表的基础上修改指针的指向定义三个指针对链表每个结点的指针进行反转循环直到链表结束。具体过程动图如下头插法在我们对链表进行进行头插时假设依次插入123三个结点最后结点的就是321刚好相反。我们可以利用这个特性对链表进行反转创建一个头指针指向一个空链表然后遍历原链表的结点将结点以头插的形式头插到新的链表中最终新链表即为我们所需的反转链表(由于在头插过程中会改变结点的指向所以我们也需要保存原链表的下一结点)。具体过程动图如下c.AC代码(迭代)struct ListNode
{int val;struct ListNode *next;
};//三指针法
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* n1 NULL;struct ListNode* n2 head;while (n2){struct ListNode* n3 n2-next; //保存下一结点位置n2-next n1;n1 n2;n2 n3;}//n2为空时n1即为反转后表头return n1;
}//头插法
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newhead NULL; //新链表struct ListNode* first head;while (first){struct ListNode* next first-next; //保存下一结点//进行头插first-next newhead;newhead first;first next;}//全部结点头插完毕return newhead;}d.题解分析(递归)除了用上面迭代的方式我们还可以用递归的方式来实现反转链表这会让代码更加简洁。我们可以先使用递归函数找到链表尾记为retret即为反转后链表的头结点。当找到头结点后递归函数开始返回每次将当前结点的下一结点的next指针指向当前结点。由于递归返回是逆向的因此当递归函数全部出栈后链表的反转也就完成了。具体过程动图如下e.AC代码(递归)struct ListNode
{int val;struct ListNode *next;
};
//递归法
struct ListNode* reverseList(struct ListNode* head)
{if (head NULL || head-next NULL) //当只有一个结点、没有结点、递归到最后一个结点时返回return head;struct ListNode* cur reverseList(head-next); //找到链表尾结点head-next-next head; //让下一结点指向当前结点head-next NULL; //当前结点指向空return cur; //返回反转后头结点
}链表的中间结点a.题目b.题解分析本题我们可以使用快慢指针的方法来解答。✈快慢指针含快指针和慢指针两个指针。快慢指针中的快慢指的是移动的步长即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2次慢指针每次向前移动1次。由于我们要求找到链表的中间结点所以我们先定义一个快指针fast和一个慢指针slow指向第一个结点然后让指针开始移动。规定快指针每次移动两步慢指针每次移动一步当快指针走到“链表尾”后由于慢指针移动的步长为快指针一半最后慢指针指向的即为链表的中间结点。本题有个需要注意的地方是当链表的结点数为奇数时链表只有一个中间结点当快指针走到尾结点时慢指针即指向中间结点但当链表的结点数为偶数时快指针不可能走到尾结点并且链表有两个中间结点由于题目要求我们返回第二个结点对应快指针指向空。综上快指针fast移动停止的条件是fast NULL || fast - next NULL。具体动图过程如下c.AC代码struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow head;struct ListNode* fast head;while (fast ! NULL fast-next ! NULL) //循环继续条件对应于上述结束条件{fast fast-next-next;slow slow-next;}return slow;
}合并两个有序链表a.题目b.题解分析这道题和合并两个有序数组有异曲同工之妙只不过我们要合并的是链表而不是数组。我们可以从左到右遍历两个链表比较结点的大小将小的结点尾插到新链表。注意不是创建一个新结点然后尾插题目要求新链表是通过已有结点拼接而成的。当一个链表遍历完毕后将另外一个链表的剩余结点尾插到新链表后即可完成合并。我们在前面学习链表尾插时不难发现如果链表没有带哨兵位的头结点尾插时需要额外考虑链表为空的情况而我们正是需要从空链表开始尾插所以为了代码简洁我们可以创建带哨兵位的头结点来指向链表的有效部分这样可以不需要进行分类讨论。具体过程动图如下c.AC代码struct ListNode
{int val;struct ListNode *next;};
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* head malloc(sizeof(struct ListNode)); //创建头结点head-next NULL;struct ListNode* tail head; //tail代表尾结点struct ListNode* p1 list1;struct ListNode* p2 list2;//遍历比较尾插while (p1 ! NULL p2 ! NULL){if (p1-val p2-val){//把list2尾插到tail结点后tail-next p2;tail tail-next;p2 p2-next;}else{//把list1尾插到tail结点后tail-next p1;tail tail-next;p1 p1-next;}}//有一个链表遍历完毕if (p1){//将p1及以后结点尾插tail-next p1;}else if (p2){//将p2及以后结点尾插tail-next p2;}struct ListNode* cur head-next; //头结点指向的部分即为我们所需的结果free(head); //释放创建的头结点return cur;
} 以上就是本期的全部内容啦制作不易能否点个赞再走呢
