题解 | #牛群旋转#
牛群旋转
https://www.nowcoder.com/practice/5137e606573843e5bf4d8ea0d8ade7f4
考察的知识点:遍历链表、修改节点的指针指向;
解答方法分析:
- 创建两个新的链表节点
small
和large
,作为分割后的链表的头节点。 - 使用两个指针
sHead
和lHead
分别指向small
和large
的初始位置,以便最后返回结果。 - 遍历原始链表
head
,若当前节点的值小于x
,则将其连接到small
链表的末尾,并更新指针small
。否则,将其连接到large
链表的末尾,并更新指针large
。 - 遍历完成后,将
large
链表的末尾指向NULL
(表示结束),并将small
链表的末尾连接到large
链表的开头,即small->next = lHead->next
。 - 最后返回
sHead->next
,即分割后的链表的头节点。
所用编程语言:C++;
完整编程代码:↓
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* rotateLeft(ListNode* head, int k) { if (!head || k == 0) { return head; } ListNode* cur = head; int length = 0; while (cur) { ++length; cur = cur->next; } k %= length; if (k == 0) { return head; } ListNode* fast = head; ListNode* slow = head; while (k--) { fast = fast->next; } while (fast->next) { fast = fast->next; slow = slow->next; } fast->next = head; head = slow->next; slow->next = nullptr; return head; } };