25. Reverse Nodes in k-Group
in 25 group reverse nodes
2023-09-11 14:22:48 时间
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
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
Note:
- Only constant extra memory is allowed.
- You may not alter the values in the list's nodes, only nodes itself may be changed.
code:
using a stack
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { stack<ListNode*> s; ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* current = dummy; ListNode* next = dummy->next; while (next) { for (int i = 0; i < k && next != NULL; ++i) { s.push(next); next = next->next; } if (s.size() != k) return dummy->next; while (!s.empty()) { current->next = s.top(); s.pop(); current = current->next; } current->next = next; } return dummy->next; } };
Runtime: 24 ms, faster than 32.59% of C++ online submissions for Reverse Nodes in k-Group.
this isn't conform with this question's demand.
the right way:
class Solution { public: ListNode *reverseKGroup(ListNode *head, int k) { if(head==NULL||k==1) return head; int num=0; ListNode *preheader = new ListNode(-1); preheader->next = head; ListNode *cur = preheader, *nex, *pre = preheader; while(cur = cur->next) num++; while(num>=k) { cur = pre->next; nex = cur->next; for(int i=1;i<k;++i) { cur->next=nex->next; nex->next=pre->next; pre->next=nex; nex=cur->next; } pre = cur; num-=k; } return preheader->next; } };
Runtime: 28 ms, faster than 16.72% of C++ online submissions for Reverse Nodes in k-Group.
it will have a difficulty to understand.
相关文章
- Python3中遇到UnicodeEncodeError: 'ascii' codec can't encode characters in ordinal not in range(128)
- 【MySQL】in GROUP BY clause; this is incompatible with sql_mode=only_full_group_by
- [Algorithm] Count occurrences of a number in a sorted array with duplicates using Binary Search
- [Python] Reuse Code in Multiple Projects with Python Modules
- [Ionic2] Device Interaction in an Ionic App with Cordova Plugins
- sharepoint2010:The number of items in this list exceeds the list view threshold, which is 20000 items.
- [Typescript] Tips: Use 'in' operator to transform a union to another union(watched)
- [Algorithm] Count Negative Integers in Row/Column-Wise Sorted Matrix
- [Javascript] Decorators in JavaScript
- [TypeScript] What's New in TypeScript 1.4
- [LeetCode] Find Minimum in Rotated Sorted Array II
- 【34】报错error:(-212:Parsing error)skipSpaces in function ‘src/VINS-Fusion/config/OAK-D/config.yaml(25)
- why product overview page could not be displayed in QI2 506
- create PDF in console with no environment variable set
- how CRM One Order search by contact name work in the past
- Matlab:成功解决In an assignment A(I)=B,the number of elements in B and I must be the same
- Spark SQL 源代码分析之 In-Memory Columnar Storage 之 in-memory query
- Patches in Electron