安微省建设庁官方网站,购买服务器后如何做网站,图片编辑器在线,做网站技术含量文章目录前言反转链表合并两个有序链表写在最后前言 上一章讲解了单链表 - 传送门 - #xff0c;后面几章就对单链表进行一些简单的题目练习#xff0c;目的是为了更好的理解单链表的实现以及加深对某些函数接口的熟练度。 本章带来了两个题目。一是反转链表#x…
文章目录前言反转链表合并两个有序链表写在最后前言 上一章讲解了单链表 - 传送门 - 后面几章就对单链表进行一些简单的题目练习目的是为了更好的理解单链表的实现以及加深对某些函数接口的熟练度。 本章带来了两个题目。一是反转链表二是合并两个有序链表整体难度不大但要理清解题思路。
反转链表
题目链接 - 传送门 -
该题目的意思是将一个单链表反转过来单链表的尾节点变成新的头节点头节点变成新的尾节点 题目描述是给你一个单链表的头节点 head 请你反转链表并返回反转后的链表。 返回反转后的链表也就是返回反转后的链表的头节点。
思路一
创建一个新的链表取原链表的元素依次头插即可最后返回这个新的链表的头节点。 思路二 直接修改原链表返回原链表的尾节点反转后的头节点即可。 定义三个指针遍历原链表三个指针 prevcurtail prev开始指向NULLcur指向头节点tail指向cur 的下一个节点(为了找到下一个)。具体操作就是cur-next prev将指针改变指向然后prev curcur tailtail cur-next(该语句在循环的开头)。这样又是三个指针指向不同的节点然后再将cur的指针指向前一个prev整个过程其实就是一个循环。 循环的条件是cur不为NULL就继续当cur为空也就是最后一步cur tail此时curtail都为空而prev刚好指向原链表的最后一个节点所以最后返回prev就可以了。 这里采用思路二进行代码实现
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur head;struct ListNode* prev NULL;while (cur){struct ListNode* tail cur-next;cur-next prev;prev cur;cur tail;}return prev;
}合并两个有序链表
题目链接 - 传送门 -。
题目描述将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 该题与归并排序的排序思路差不多。本题需要创建一个新链表。之后采用双指针分别遍历上下两个链表那个节点的数据较小就在新的链表中尾插该节点然后指向该节点的指针向后移动一位。整体来说就是一个循环循环结束的条件就是两个指针都指向了NULL或者其中一个指针指向了NULL。 注意我们这里的新链表是不带哨兵位的当然带哨兵位可能更加方便最后需要返回哨兵位的下一个节点的指针。 如果循环结束后有一个指针没有指向NULL那么在后面还需要将剩余的节点依次尾插直到两个指针都为NULL合并成功。 代码实现
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* l1 list1, * l2 list2; // 两个指针分别指向两个链表的头struct ListNode* head NULL, * cur NULL; // 新链表的头和进行操作的指针curwhile (l1 l2) // 有一个指向空就结束{if (l1-val l2-val) // 比较数据值{if (!head) head cur l1; // 这个if是如果新链表为空就将该节点作为头节点else cur-next l1, cur cur-next;l1 l1-next;}else{if (!head) head cur l2;else cur-next l2, cur cur-next;l2 l2-next;}}// 如果l1不为空说明l1还有节点没有尾插完需继续尾插while (l1){if (!head) head cur l1;else cur-next l1, cur cur-next;l1 l1-next;}// 如果l2不为空说明l2还有节点没有尾插完需继续尾插while (l2){if (!head) head cur l2;else cur-next l2, cur cur-next;l2 l2-next;}// 最后返回新链表的头节点return head;
}写在最后 对于单链表的题目练习最重要的是思路我们在数据结构阶段要养成画图的习惯因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。 感谢阅读本小白的博客错误的地方请严厉指出噢
