网站建设中模板 模板无忧,外贸网站页面用什么做最好,常州谷歌优化,中国设计师联盟网站链表 1. 相交链表2. 反转链表3. 回文链表4. 环形链表5. 合并两个有序链表 1. 相交链表
给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null 。
// 题解#xff1a;使用A/B循环遍… 链表 1. 相交链表2. 反转链表3. 回文链表4. 环形链表5. 合并两个有序链表 1. 相交链表
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
// 题解使用A/B循环遍历路径之和a(b-c)b(a-c)则存在交点
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* A headA;ListNode* B headB;while (A ! B) {A A ! nullptr ? A-next : headB;B B ! nullptr ? B-next : headA;}return A;
}2. 反转链表
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
// 题解保存上次的值并反转
ListNode* reverseList(ListNode* head) {ListNode* pre_node nullptr;ListNode* cur_node head;while (cur_node ! nullptr) {ListNode* temp_node cur_node-next;cur_node-next pre_node;pre_node cur_node;cur_node temp_node;}return pre_node;
}3. 回文链表
给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false
// 题解使用快慢指针对前半部分链表反转
bool isPalindrome(ListNode* head) {ListNode* slow_node head;ListNode* fast_node head;ListNode* pre_node nullptr;LisetNode* rev_node head;while (fast fast_node-next) {rev_node slow_node;slow_node slow_node-next;fast_node fast_node-next-next; // 快慢指针找到中间值rev_node-next pre_node; // 链表反转pre_node rev_node;}if (fast_node ! nullptr) {slow_node slow_node-next; // 奇数节点跳过}while (rev_node) {if (rev_node-val ! slow_node-val) {return false;}rev_node rev_node-next;slow_node slow_node-next;}return true;
}4. 环形链表
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
// 题解快慢指针可以循环查找
bool hasCycle(ListNode *head) {ListNode* slow_node head;LiseNode* fast_node head;while (fast_node fast_node-next) {slow_node slow_node-next;fast_node fast_node-next-next;if (slow_node fast_node) {return true;}}return false;
}5. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
// 题解由于有序因此可新创建链表按照升序连接即可
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* cur_node new ListNode(-1);ListNode* result_node cur_node; // 用于返回while (list1 ! nullptr list2 ! nullptr) {if (list1-val list2-val) {cur_node-next list1;list1 list1-next;} else {cur_node-next list2;list2 list2-next;}cur_node cur_node-next;}cur_node-next list1 ! nullptr ? list1 : list2;return result_node;
}
