12.25 - 重排链表 NULL与nullptr的区别

目录

1.重排链表

a.核心思想

b.思路

c.步骤

2.NULL与nullptr的区别

1.重排链表

143. 重排链表 - 力扣（LeetCode）https://leetcode.cn/problems/reorder-list/

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr != nullptr) { ListNode* nextTemp = curr->next; curr->next = prev; prev = curr; curr = nextTemp; } return prev; } void reorderList(ListNode* head) { // 处理特殊情况 if (head == nullptr || head->next == nullptr) return; // 找到链表的中点 ListNode* slow = head; ListNode* fast = head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } // 反转后半部分链表 ListNode* secondHead = reverseList(slow->next); slow->next = nullptr; // 合并两个链表 ListNode* p1 = head; ListNode* p2 = secondHead; while (p2 != nullptr) { ListNode* temp1 = p1->next; ListNode* temp2 = p2->next; p1->next = p2; p2->next = temp1; p1 = temp1; p2 = temp2; } } };

a.核心思想

通过找到链表的中点，将链表分为前后两部分，对后半部分进行反转，然后合并前后两部分，在合并过程中将后半部分的节点逐个插入到前半部分的相邻节点之间，从而实现重排链表的目的。

b.思路

① 找到链表的中点：使用快慢指针法，快指针每次走两步，慢指针每次走一步，当快指针到达链表末尾时，慢指针指向的就是链表的中点。

② 反转后半部分链表：从慢指针的下一个节点开始，反转后半部分链表。

③ 合并链表：将前半部分链表和反转后的后半部分链表进行合并，将后半部分的节点逐个插入到前半部分的相邻节点之间。

c.步骤

① 使用快慢指针找到链表的中点。

② 反转后半部分链表。

③ 合并两个链表。

2.NULL与nullptr的区别

希望这些内容对大家有所帮助！

感谢大家的三连支持！