328. Odd Even Linked List
- Odd Even Linked List:题目链接
相似题目86. Partition List:题目链接
基本思想:在遍历head的同时，创建两个链表，(dummy_1)用来存放位置为奇数的节点，(dummy_2)用来存放位置为偶数的节点，最后将dummy_2的最后一个节点指针域置为NULL，被链接到dummy_1的最后一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| // 时间复杂度O(N) 空间复杂度O(1)
LinkNode * oddEvenList(struct ListNode* head) {
LinkNode *dummy_1 = (LinkNode *) malloc(sizeof(LinkNode)); // 设立带头结点的链表 存放位置为奇数的节点
LinkNode *dummy_2 = (LinkNode *) malloc(sizeof(LinkNode)); // 设立带头结点的链表 存放位置为偶数的节点
LinkNode *curNode_1 = dummy_1, *curNode_2 = dummy_2;
int count = 1; // 计数器
while (head) {
if (0 != count % 2) {
curNode_1->next = head;
curNode_1 = head;
}else{
curNode_2->next = head;
curNode_2 = head;
}
head = head->next;
count++;
}
curNode_2->next = NULL; // dummy_2要接在dummy_1的后面，当然要将整体的最后一个元素的指针域置为NULL
curNode_1->next = dummy_2->next;
return dummy_1->next;
}
|
pS: 源代码链接
