We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
题目描述:
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL
解题思路:刚开始看到题目,看到k可以通过与链表长度求余来减少循环的次数,然后循环k%length次,每一次把最后一个节点移到前面。后来觉得这可能不是最优的,就看了网上的。发现可以用快慢指针。自己完全都没想到用快慢指针,虽然之前写过几题用过。快指针先往前移动k,然后slow开始从head移动,fast与slow同时移动,当fast为空时,slow就是当前要截断的节点了。
C解题:
struct ListNode* rotateRight(struct ListNode* head, int k){ if(!head) return NULL; if(!k || !head->next) return head; int length = 0; struct ListNode* tmp_head = head,*fast = head,*slow = head,*slow_pre = NULL,*fast_pre = NULL; while(tmp_head){ length++; tmp_head = tmp_head->next; } int trueK = k%length; if(!trueK) return head; tmp_head = head; while (trueK) { fast = fast->next; trueK--; } // 跑完循环,slow是需要截断的头结点 while (fast) { slow_pre = slow; slow = slow->next; fast_pre = fast; fast = fast->next; } slow_pre->next = NULL; fast_pre->next = head; return slow; }
The text was updated successfully, but these errors were encountered:
No branches or pull requests
题目描述:
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
示例 1:
示例 2:
解题思路:刚开始看到题目,看到k可以通过与链表长度求余来减少循环的次数,然后循环k%length次,每一次把最后一个节点移到前面。后来觉得这可能不是最优的,就看了网上的。发现可以用快慢指针。自己完全都没想到用快慢指针,虽然之前写过几题用过。快指针先往前移动k,然后slow开始从head移动,fast与slow同时移动,当fast为空时,slow就是当前要截断的节点了。
C解题:
The text was updated successfully, but these errors were encountered: