328.奇偶鏈表

題目描述

思路、算法及代碼實(shí)現(xiàn)

方法：分離節(jié)點(diǎn)后合并
如果鏈表為空，則直接返回鏈表。
對(duì)于原始鏈表，每個(gè)節(jié)點(diǎn)都是奇數(shù)節(jié)點(diǎn)或偶數(shù)節(jié)點(diǎn)。頭節(jié)點(diǎn)是奇數(shù)節(jié)點(diǎn)，頭節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)是偶數(shù)節(jié)點(diǎn)，相鄰節(jié)點(diǎn)的奇偶性不同。因此可以將奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分離成奇數(shù)鏈表和偶數(shù)鏈表，然后將偶數(shù)鏈表連接在奇數(shù)鏈表之后，合并后的鏈表即為結(jié)果鏈表。
原始鏈表的頭節(jié)點(diǎn)head也是奇數(shù)鏈表的頭節(jié)點(diǎn)以及結(jié)果鏈表的頭節(jié)點(diǎn)，head的后一個(gè)節(jié)點(diǎn)是偶數(shù)鏈表的頭節(jié)點(diǎn)。令evenHead = head.next，則evenHead是偶數(shù)鏈表的頭節(jié)點(diǎn)。
維護(hù)兩個(gè)指針odd和even分別指向奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)，初始時(shí)odd = head,even = evenHead。通過(guò)迭代的方式將奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分離成兩個(gè)鏈表，每一步首先更新奇數(shù)節(jié)點(diǎn)，然后更新偶數(shù)節(jié)點(diǎn)。
1、更新奇數(shù)節(jié)點(diǎn)時(shí)，奇數(shù)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)是偶數(shù)節(jié)點(diǎn)，需要指向偶數(shù)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，因此令odd.next = even.next，然后令odd = odd.next，此時(shí)odd變成even的后一個(gè)節(jié)點(diǎn)。
2、更新偶數(shù)節(jié)點(diǎn)時(shí)，偶數(shù)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)是奇數(shù)節(jié)點(diǎn)，需要指向奇數(shù)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，因此令even.next = odd.next，然后令even = even.next，此時(shí)even變成odd的后一個(gè)節(jié)點(diǎn)。
在上述操作之后，即完成了對(duì)一個(gè)奇數(shù)節(jié)點(diǎn)和一個(gè)偶數(shù)節(jié)點(diǎn)的分離。全部節(jié)點(diǎn)分離完畢的條件是even為空節(jié)點(diǎn)或者even.next為空節(jié)點(diǎn)，此時(shí)odd指向最后一個(gè)奇數(shù)節(jié)點(diǎn)。
最后令odd.next = evenHead，將偶數(shù)鏈表連接在奇數(shù)鏈表之后，即完成了奇數(shù)鏈表和偶數(shù)鏈表的合并，結(jié)果鏈表的頭節(jié)點(diǎn)仍然是head。

總結(jié)

以上是生活随笔為你收集整理的Leetcode每日一题2020.11.13第328题：奇偶链表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。