c++-c++编程基础之leetcode题解第61题旋转链表.zip资源-CSDN下载

共1个文件

md：1个

需积分: 1 169 浏览量 2024-04-09 04:49:41 上传评论收藏 2KB ZIP 举报

在C++编程中，LeetCode是一个非常受欢迎的在线平台，用于练习和提升编程技能，特别是算法和数据结构。第61题"旋转链表"是其中一道经典的问题，旨在考察开发者对链表操作的熟练程度以及对问题解决的逻辑思维能力。本资料包可能包含了关于这道题目的详细解答，包括代码实现、思路解析等。让我们深入理解题目。旋转链表的任务是将给定的链表按一个给定的整数k逆时针旋转。例如，如果链表1->2->3->4->5，且k=2，那么旋转后的链表应为4->5->1->2->3。链表的旋转需要在原地完成，也就是说，不能使用额外的数据结构，而且必须保持原有的元素顺序。解决这个问题的关键在于理解链表的性质和如何有效地进行旋转操作。以下是一种可能的解题思路： 1. **检查基本情况**：我们需要处理特殊情况，如空链表或k等于0的情况，此时无需做任何旋转。 2. **计算链表长度**：我们需要知道链表的长度，以便确定旋转的次数。可以通过遍历链表，每遇到一个节点计数加一，直到达到头节点（即当前节点的next指针为nullptr）。 3. **找到新的头节点和尾节点**：由于我们是逆时针旋转，旋转k次实际上相当于将链表的最后k个节点移动到前面。因此，我们需要找到链表的尾部，并通过k模链表长度得到实际需要移动到头部的节点。 4. **断开链接**：断开尾部节点与前一个节点的链接，形成一个新的循环链表。 5. **重新连接链表**：将新的尾部节点的next指针指向原头节点，然后将原头节点的next指针指向之前尾部节点的前一个节点，这样就完成了旋转。 6. **返回新头节点**：返回新的头节点，即原来链表的第k个节点。在C++中，链表通常用结构体或类来表示，包含一个数据域和一个指向下一个节点的指针。例如： ```cpp struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ``` 解题代码可能会涉及到创建辅助指针，如`prev`和`curr`，逐步遍历链表并执行上述步骤。在实际编写代码时，需要注意边界条件的处理，避免空指针异常，并确保所有指针都被正确地更新，以维持链表的完整性。本资料包中的内容很可能是针对LeetCode第61题“旋转链表”的C++解决方案，包括了详细的解题思路、代码实现和可能的测试用例。对于学习C++编程，尤其是提升算法能力的初学者来说，这是一个很好的学习资源。通过深入理解和实践这样的题目，可以增强对链表操作的理解，同时提升问题解决的技巧。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第61题旋转链表.zip （1个子文件）

c++_c++编程基础之leetcode题解第61题旋转链表

README.md 3KB

# [61. Rotate List (Medium)](https://leetcode.com/problems/rotate-list/) Given the <code>head</code> of a linked list, rotate the list to the right by <code>k</code> places.   Example 1: <img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/rotate1.jpg" style="width: 450px; height: 191px;"> <pre>Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3] </pre> Example 2: <img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/roate2.jpg" style="width: 305px; height: 350px;"> <pre>Input: head = [0,1,2], k = 4 Output: [2,0,1] </pre>   Constraints: <ul> <li>The number of nodes in the list is in the range <code>[0, 500]</code>.</li> <li><code>-100 <= Node.val <= 100</code></li> <li><code>0 <= k <= 2 * 109</code></li> </ul> **Companies**: [Microsoft](https://leetcode.com/company/microsoft), [Amazon](https://leetcode.com/company/amazon), [Bloomberg](https://leetcode.com/company/bloomberg) **Related Topics**: [Linked List](https://leetcode.com/tag/linked-list/), [Two Pointers](https://leetcode.com/tag/two-pointers/) **Similar Questions**: * [Rotate Array (Medium)](https://leetcode.com/problems/rotate-array/) * [Split Linked List in Parts (Medium)](https://leetcode.com/problems/split-linked-list-in-parts/) ## Solution 1. ```cpp // OJ: https://leetcode.com/problems/rotate-list/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(1) class Solution { int getLength(ListNode *head) { int ans = 0; for (; head; head = head->next) ++ans; return ans; } public: ListNode* rotateRight(ListNode* head, int k) { if (!head) return nullptr; int len = getLength(head); k %= len; if (k == 0) return head; auto p = head, q = head; while (k--) q = q->next; while (q->next) p = p->next, q = q->next; auto ans = p->next; p->next = nullptr; q->next = head; return ans; } }; ``` ## Solution 2. ```cpp // OJ: https://leetcode.com/problems/rotate-list/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(1) class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if (!head) return nullptr; int len = 1; auto p = head; while (p->next) p = p->next, ++len; p->next = head; k = len - k % len; while (k--) p = p->next; auto ans = p->next; p->next = nullptr; return ans; } }; ```

评论收藏

内容反馈