首页 > 代码库 > leetcode - Rotate List
leetcode - Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
这个题目主要是要理解清楚rotate的含义，这个含义和二进制数的右移有点类似，不过这里补高位的数是右移出去的数
个人思路：
1，先计算链表长度，记为listSize，可以发现若k等于listSize时，右移之后的链表与原链表是相同的，因此实际的移动量为k % listSize，若k % listSize等于0，就说明右移之后的链表等于原链表，直接返回原链表即可
2，若k % listSize在1到listSize - 1之间，则需要定位出两部分链表的边界，由于右半部分的链表长度是k % listSize，且总长度是listSize，所以左半部分的链表长度为listSize - k % listSize，从链表头部开始遍历，即可得到边界结点，然后重新连接这两个链表即可
代码：
1 #include <stddef.h> 2 3 struct ListNode 4 { 5 int val; 6 ListNode *next; 7 ListNode(int x) : val(x), next(NULL) {} 8 }; 9 10 class Solution {11 public:12 ListNode *rotateRight(ListNode *head, int k) {13 if (!head)14 {15 return NULL;16 }17 18 ListNode *current = head;19 ListNode *tail = NULL; //链表尾结点20 int listSize = 0; //链表长度21 22 while (current) //计算链表长度23 {24 if (!current->next)25 {26 tail = current;27 }28 current = current->next;29 ++listSize;30 }31 32 k = k % listSize; //计算实际的移动量33 34 if (k == 0) //若k等于0，则返回原链表35 {36 return head;37 }38 39 current = head;40 41 for (int i = 1; i < (listSize - k); ++i) //定位到链表断开的位置42 {43 current = current->next;44 }45 46 ListNode *leftHead = head;47 ListNode *leftTail = current;48 ListNode *rightHead = current->next;49 ListNode *rightTail = tail;50 51 //旋转链表52 leftTail->next = NULL;53 rightTail->next = leftHead;54 head = rightHead;55 56 return head;57 }58 };
网上基本上是这个思路
leetcode - Rotate List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。