首页 > 代码库 > Reverse Nodes in k-Group
Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
再链表中，每k个节点逆置，设置一个头节点，便于插入，向后寻找k个节点，将k个节点逆置，再将这k个节点接回原来的链表，继续寻找下一个k个节点逆置。。。
由于每次都扫描了两遍kgroup的节点，即扫描了两遍原链表，时间复杂度为O(n)
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *reverseKGroup(ListNode *head, int k) {12 if( !head || k<2 ) return head;13 ListNode node(-1); //设置头结点14 node.next = head;15 ListNode* ppre = &node; //ppre及其前面的节点都已经逆置成功16 while( ppre->next ) { //从ppre下一个节点开始寻找17 ListNode* tail = ppre->next;18 ListNode* pre = ppre;19 int cnt = 0;20 while( tail && cnt<k ) { //寻找k个节点，tail指向第k+1个节点21 pre = pre->next;22 tail = tail->next;23 ++cnt;24 }25 if( cnt != k ) return node.next; //如果后面的节点数不满k个，说明逆置完成26 //如果cnt为k，说明符合逆置条件，同时tail可能为空，也可能不为空27 pre->next = 0; //令tail成一段新的链表28 head = ppre->next->next; //kgroup中的第一个节点时逆置后链表的第一个节点29 ppre->next->next = tail; //连上tail30 pre = ppre->next; //保存逆置后链表中tail的前驱指针31 while( head ) { //使用头插法，逆置链表32 ListNode* p = head;33 head = head->next;34 p->next = ppre->next;35 ppre->next = p;36 }37 ppre = pre; //移向新链表38 }39 return node.next;40 }41 };
Reverse Nodes in k-Group
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。