Reorder List [leetcode] 这两种思路
2023-09-27 14:27:02 时间
第一个想法随着vector保存全部Node*
表拼接出来
void reorderList(ListNode *head) { vector<ListNode*> content; ListNode * cur = head; while (cur) { content.push_back(cur); cur = cur->next; } int size = content.size(); cur = NULL; for (int i = 0; i <= size - 1 - i; i++) { if (cur) cur->next = content[i]; if (i != size - i - 1) content[i]->next = content[size - 1 - i]; cur = content[size - 1 - i]; } if (cur) cur->next = NULL; }
另外一种思路能够分成下面几个步骤:
1. 找到中间的节点nMid
2. 翻转nMid到末尾的链表
3. 拼接head和nMid
代码例如以下
void reorderList(ListNode *head) { if (head == NULL) return; ListNode * mid = head; ListNode * endOfHead; ListNode * end = head; while (end) { end = end->next; endOfHead = mid; mid = mid->next; if (end) end = end->next; } endOfHead->next = NULL;//end of first half //reverse if (mid == NULL) return; ListNode* p0, * p1, * p2; p1 = mid; p2 = mid->next; p1->next = NULL; while (p2) { p0 = p1; p1 = p2; p2 = p2->next; p1->next = p0; } mid = p1; //concat ListNode * newHead = head; while (mid && head) { head = head->next; newHead->next = mid; newHead = newHead->next; mid = mid->next; newHead->next = head; newHead = newHead->next; } }
版权声明:本文博主原创文章。博客,未经同意不得转载。
相关文章
- 【LeetCode】最小覆盖子串 [H](滑动窗口)
- leetcode 382 Linked List Random Node
- leetCode 61.Rotate List (旋转链表) 解题思路和方法
- LeetCode[Linked list]: Rotate List
- LeetCode_贪心算法_中等_769.最多能完成排序的块
- LeetCode_数据结构设计_中等_146.LRU 缓存
- 【Leetcode 346/700】79. 单词搜索 【中等】 回溯深度搜索JavaScript版
- LeetCode·每日一题·1598.文件夹操作日志收集器·栈模拟
- Codewars, Leetcode, Hackerrank. Online Judges Reviews
- Remove Duplicates from Sorted List II--LeetCode
- LeetCode Merge Two Sorted Lists
- LeetCode: Multiply Strings. Java
- LeetCode || Copy List with Random Pointer
- [LeetCode] 382. Linked List Random Node 链表随机节点
- [LeetCode] 25. Reverse Nodes in k-Group 每k个一组翻转链表
- [LeetCode] 803. Bricks Falling When Hit 打击砖块掉落
- [LeetCode] 486. Predict the Winner 预测赢家
- [LeetCode] 142. Linked List Cycle II 链表中的环 II
- [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项 II
- [LeetCode] 206. Reverse Linked List 反向链表
- leetcode 227 基本计算器II
- leetcode 46 全排列
- leetcode 383 赎金信