苏州网站建设风兰,怎么用网页源码做网站,学动漫制作专业后悔吗,建行24小时人工电话328. 奇偶链表#xff08;中等#xff09; 思路 如果链表为空#xff0c;则直接返回链表。 对于原始链表#xff0c;每个节点都是奇数节点或偶数节点。头节点是奇数节点#xff0c;头节点的后一个节点是偶数节点#xff0c;相邻节点的奇偶性不同。因此可以将奇数节点和偶…328. 奇偶链表中等 思路 如果链表为空则直接返回链表。 对于原始链表每个节点都是奇数节点或偶数节点。头节点是奇数节点头节点的后一个节点是偶数节点相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表然后将偶数链表连接在奇数链表之后合并后的链表即为结果链表。 原始链表的头节点 head 也是奇数链表的头节点以及结果链表的头节点head 的后一个节点是偶数链表的头节点。令 evenHead head-next则 evenHead 是偶数链表的头节点。 维护两个指针 odd 和 even 分别指向奇数节点和偶数节点初始时 odd headeven evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表每一步首先更新奇数节点然后更新偶数节点。 在上述操作之后即完成了对一个奇数节点和一个偶数节点的分离。重复上述操作直到全部节点分离完毕。全部节点分离完毕的条件是 even 为空节点或者 even-next 为空节点此时 odd 指向最后一个奇数节点即奇数链表的最后一个节点。 最后令 odd-next evenHead将偶数链表连接在奇数链表之后即完成了奇数链表和偶数链表的合并结果链表的头节点仍然是 head。
代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* oddEvenList(ListNode* head) {if(!head) return head;ListNode *EvenHead head-next;ListNode *odd head, *even head-next;while(odd even odd-next even-next) {odd-next even-next;even-next even-next-next;odd odd-next;even even-next;}odd-next EvenHead;return head;}
};参考资料
力扣官方题解
