LeetCode热题100——链表

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

6. 环形链表Ⅱ

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

// 题解：快慢指针遍历，找到相同节点后，从头开始遍历
ListNode *detectCycle(ListNode *head) {ListNode* slow = head;ListNode* fast = head;while (fast && fast->next) {fast = fast->next->next;slow = slow->next;if (fast == slow) {ListNode* cur_node = head;while (cur_node != slow) {cur_node = cur_node->next;slow = slow->next;}return slow;}}return nullptr;
}

7. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。

// 题解：需要注意进位
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* head = new ListNode();ListNode* res_node = head;int carry = 0; //进位while (l1 || l2 || carry) {int n1 = l1 != nullptr ? l1->val : 0;int n2 = l2 != nullptr ? l2->vale : 0;int sum = carry + n1 + n2;carry = sum / 10;res_node->next = new ListNode(sum % 10);res_node = res_node->next;if (l1) l1 = l1->next;if (l2) l2 = l2->next;}return head->next;
}