[LeetCode] Reverse Nodes in k-Group
LeetCode in group reverse nodes
2023-09-11 14:17:25 时间
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
思路: 先实现reverseList(head), 然后实现reverse(start, end)反正从start到end的链表,然后基于reverse(start,end)来完成最后的动作。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *reverse(ListNode* head) { if(head == NULL) return NULL; ListNode * pre = NULL; ListNode * cur = head; ListNode * next = NULL; // make cur->next = pre; while(cur) { next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } #if 1 ListNode* reverse(ListNode* head, ListNode* end) { if(head == NULL) return NULL; ListNode * pre = NULL; ListNode * cur = head; ListNode * next = NULL; // make cur->next = pre; while(cur) { next = cur->next; cur->next = pre; pre = cur; cur = next; if(pre == end) break; } return pre; } ListNode *reverseKGroup(ListNode *head, int k) { if(head == NULL) return NULL; ListNode dummy(-1); dummy.next = head; ListNode* pre = &dummy; ListNode* start= head; ListNode* end = start; ListNode* next= NULL; int cnt = 0; while(end) { cnt++; if(cnt == k) { next = end->next; //assign pre->next = reverse(start, end); start->next = next; //cout << "start\t" << start->val <<endl; //cout << "end\t" << end->val <<endl; //printList(dummy.next); //printList(pre->next); //update pre = start; start = next; end = next; cnt = 0; //cout << "start\t" << start->val <<endl; //cout << "end\t" << end->val <<endl; //cout << "pre\t" << pre->val <<endl; } else end = end->next; } return dummy.next; } #endif };
相关文章
- Java实现 LeetCode 561 数组拆分 I(通过排序算法改写PS:难搞)
- Java实现 LeetCode 559 N叉树的最大深度(遍历树,其实和便利二叉树一样,代码简短(●ˇ∀ˇ●))...
- Java实现 LeetCode 329 矩阵中的最长递增路径
- Java实现 LeetCode 216. 组合总和 III(三)
- SQL Server实现 LeetCode 178 分数排名
- Java实现 LeetCode 146 LRU缓存机制
- LeetCode(115):不同的子序列
- (LeetCode 153)Find Minimum in Rotated Sorted Array
- [LeetCode] Longest Increasing Path in a Matrix
- LeetCode(83): 删除排序链表中的重复元素
- LeetCode-1832. 判断句子是否为全字母句【哈希表,位运算】
- 已解决FutureWarning: The default value of regex will change from True to False in a future version. In
- 【LeetCode Python实现】 5474. 好叶子节点对的数量(中等)
- 【LeetCode Python实现】1446. 连续字符(简单)
- Leetcode 268. 丢失的数字
- Leetcode 1598. 文件夹操作日志搜集器
- LeetCode——Populating Next Right Pointers in Each Node II
- [LeetCode] Search in Rotated Sorted Array II [36]
- Spark SQL 源代码分析之 In-Memory Columnar Storage 之 in-memory query
- Leetcode--Reverse Nodes in k-Group
- leetcode 720. Longest Word in Dictionary
- leetcode 237. Delete Node in a Linked List
- leetcode 762. Prime Number of Set Bits in Binary Representation
- leetcode 637. Average of Levels in Binary Tree
- leetcode 557. Reverse Words in a String III
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点