首页 > 代码库 > LeetCode 25. Reverse Nodes in k-Group
LeetCode 25. 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值, 如何分段反转。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #include <cstdio> #include <iostream> #include "time.h" #include<stdlib.h> #include<sstream> #include<string> using namespace std; /* 25. Reverse Nodes in k-Group */ class ListNode { public : int val; ListNode* next; ListNode( int val2){ val=val2; next=NULL; } }; class Solution { public : ListNode* reverse(ListNode* head) { ListNode* cur; //μ±?°?y?ú′|àíμ??úμ? ListNode* head_old=head; //×??aê?μ?í·?áμ? ListNode* head_front= new ListNode(-1); //×??o′′?¨μ?í·?áμ??°??μ??úμ? head_front->next=head; if (head==NULL) return NULL; while (head_old->next!=NULL){ cur=head_old->next; head_old->next=cur->next; cur->next=head_front->next; head_front->next=cur; } return head_front->next; } ListNode* reverseKGroup(ListNode* head, int k) { ListNode* head_front= new ListNode(-1); head_front->next=head; ListNode* cur=head_front; ListNode* first=NULL; ListNode* first_new=NULL; ListNode* last=NULL; ListNode* last_new=NULL; ListNode* last_old=head_front; ListNode* next_record; int count=0; int first_turn=1; //cal the num of nodes int nums=0; ListNode* tmp=head; while (tmp){ nums++; tmp=tmp->next; } //special case if (head==NULL) return NULL; if (k==1) return head; if (k==nums) return reverse(head); //ordinary case while (cur->next!=NULL){ cur=cur->next; count++; if (count==1)first=cur; else if (count==k) { last=cur; next_record=last->next; //record next element last->next=NULL; //conveninent to use reverse() first_new=reverse(first); last_new=first; last_new->next=next_record; last_old->next=first_new; last_old=last_new; count=0;cur=last_new; if (first_turn==1){ first_turn=0; head=first_new; } } } return head; } }; int main() { ListNode* head = new ListNode(1); ListNode* l1 = new ListNode(2); ListNode* l2 = new ListNode(3); ListNode* l3 = new ListNode(4); ListNode* l4 = new ListNode(5); head->next=l1; l1->next=l2; l2->next=l3; l3->next=l4; Solution s; head=s.reverseKGroup(head,3); ListNode* cur=head; while (cur!=NULL){ cout<<cur->val<< " " ; cur=cur->next; } getchar (); return 0; } |
来自为知笔记(Wiz)
LeetCode 25. Reverse Nodes in k-Group
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。