[LeetCode & 剑指 offer 刷题笔记] 目录 (持续更新中...)
328.Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
- You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
- Example 1:
- Input: 1->2->3->4->5->NULL
- Output: 1->3->5->2->4->NULL
- Example 2:
- Input: 2->1->3->5->6->4->7->NULL
- Output: 2->3->6->7->1->5->4->NULL
- Note:
- The relative order inside both the even and odd groups should remain as it was in the input.(相对顺序要保持)
The first node is considered odd(odd 为奇数, 相当于 1 序开始), the second node even and so on ...
- /*
- 问题: 在链表中, 将所有奇数序号的结点放到前面, 偶数序号的结点放在后面, 要求就地解决
- 与问题 "调整数组中奇数偶数顺序" 区别在于前者调整结点, 而后者调整的是值
- O(n),O(1)
- */
- /**
- * Definition for singly-linked list.
- * struct ListNode {
- * int val;
- * ListNode *next;
- * ListNode(int x) : val(x), next(NULL) {}
- * };
- */
- // 方法: head,evenhead. 两个链表, 再拼在一起
- class Solution
- {
- public:
- ListNode* oddEvenList(ListNode* head)
- {
- if(!head) return head;
- ListNode* odd = head; // 奇数序列结点指针与头指针
- ListNode* evenhead = head->next,*even = evenhead; // 偶数序列结点指针与头指针
- while(
- even&&even->next
- ) // 偶数序列指针判断 (循环时一般用后面的指针来判断是否结束循环) 对于走两步的指针 p 均需要判断 p 与 p->next 是否为空
- {
- odd->next = odd->next->next; // 连接奇数序列结点, 每次走两步 , 先连接前面的指针
- even->next = even->next->next;// 连接偶数序列结点
- odd = odd->next; // 指向下一个奇结点
- even = even->next;
- }
- odd->next = evenhead; // 连接奇序列链表和偶序列链表
- return head;
- }
- };
来源: http://www.bubuko.com/infodetail-2909744.html