首页 > 代码库 > Leetcode:Rotate List 链表旋转
Leetcode:Rotate List 链表旋转
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
.
解题分析:
不同于数组旋转,数组可以随机存取,数组的旋转可以巧妙的 分成两两部分递归旋转
对于链表的旋转,实际上就是把后一部分连续的尾插法插入到新的结果链表中
class Solution { public: ListNode *rotateRight(ListNode *head, int k) { assert(k >= 0); if (head == nullptr) return nullptr; ListNode* cur = head; int listLen = 0; while (cur != NULL) { ++listLen; cur = cur->next; } k %= listLen; ListNode* newHead = new ListNode(0); newHead->next = head; ListNode* resHead = new ListNode(0); ListNode* resCur = resHead; cur = newHead; for (int i = 0; i < listLen - k; ++i) { cur = cur->next; } ListNode* resTail = cur; for (int i = 0; i < k; ++i) { ListNode* nextNode = cur->next; ListNode* tmp = nextNode->next; resCur->next = nextNode; resCur = nextNode; cur->next = tmp; } resCur->next = newHead->next; resTail->next = NULL; return resHead->next; } };
需要注意以下几点:
1. K的取值,因为k值可以很大,我们可以将k对链表长度取余,因为每旋转一个链表长度相当于复原了
2. 虚拟前置结点指向链表的第一个结点,因为头节点也可能被修改,而头节点的修改操作和其余结点的操作不统一,因此采用一个虚拟的前置结点
3. 我们从虚拟的前置结点newHead前进listLen - k步达到需要移动区间的前一个节点,因为每删除一个结点需要知道其前驱指针
4. 循环之后,将原链表剩下的结点一起尾插到结果链表中,并且需要将结果链表最后一个结点的next置为NULL,即使用暂存结点 resTail->next = NULL;
5. 返回的头节点应该是虚拟的前置结点的next指针
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。