328. 奇偶链表

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 127 阅读时长 ≈ 1 分钟

考点

  • 链表的合并

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
	public:
		ListNode* oddEvenList(ListNode* head) {
			int cnt = 1;
			ListNode *dummyHeadA = new ListNode(-1), *curA = dummyHeadA, *dummyHeadB = new ListNode(-1), *curB = dummyHeadB;
			while (head != nullptr) {
				if (cnt++ % 2) {
					curA->next = head;
					curA = curA->next;
				} else {
					curB->next = head;
					curB = curB->next;
				}
				head = head->next;
			}
			curA->next = dummyHeadB->next;
			curB->next = nullptr;
			return dummyHeadA->next;
		}
};

思路

新建两个伪节点，各用来构成奇链表与偶链表

遍历链表时，奇数节点插入至奇链表，偶数节点插入至偶链表；最终将偶链表接在奇链表末尾即可