高端公司网站设计南昌seo推广
今天记录的题目：
● 24. 两两交换链表中的节点
● 19.删除链表的倒数第N个节点
● 面试题 02.07. 链表相交
● 142.环形链表II
两两交换链表中的节点
题目链接：24. 两两交换链表中的节点
这题比较简单，记录好两个节点，交换其next指向
// 两两交换，注意两个元素交换块修改连接指针的先后顺序
ListNode *swapPairNode(ListNode *head)
{if (head == nullptr || head->next == nullptr) return head;ListNode preNode;preNode.next = head;ListNode *node = &preNode;while (node->next != nullptr && node->next->next != nullptr) {ListNode * nextNode = node->next->next;ListNode *curNode = node->next;curNode->next = nextNode->next;nextNode->next = curNode;node->next = nextNode;node = node->next->next;}return preNode.next;
}
删除链表的倒数第N个节点
题目链接：19. 删除链表的倒数第 N 个结点
解题思路是利用快慢指针，先让快指针前进N步，然后快慢指针一起移动，直到快指针抵达链表末尾，此时慢指针处就是需要删除的元素。
// 快慢指针，注意fastNode 还是fastNode->next
ListNode *deleteLastNNode(ListNode *head, int n)
{ListNode tmpNode;tmpNode.next = head;ListNode* preNode = &tmpNode;ListNode* fastNode = head;while (fastNode != nullptr && n-- > 0) {fastNode = fastNode->next;}if (n > 0) { // 说明链表长度小于nreturn head;}while (fastNode != nullptr) {fastNode = fastNode->next;preNode = preNode->next;}// 删除元素 preNode 的下一个元素preNode->next = preNode->next->next;return tmpNode.next;
}
链表相交
题目链接：面试题 02.07. 链表相交
环形链表 II
题目链接：142. 环形链表 II