LeetCode热题100——链表

链表"/>

LeetCode热题100——链表

链表

• 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;
}