LeetCode 328. Odd Even Linked List

この記事はLeetCode331の解答を参考にしたものです。
元の問題：https://leetcode.com/problems/odd-even-linked-list/
元の解答：https://leetcode.com/problems/odd-even-linked-list/discuss/78079/Simple-O(N)-time-O(1)-space-Java-solution.

問題

リストが与えられるので偶数番目のノード列が奇数番目のノード列の後ろに来るように編集してください。

ex. 1->2->3->4->5 => 1->3->5->2->4

解説

特に難しいことを考える必要はない。evenとoddの２つのリストを作ってodd->evenの順につないでheadを返せば良い。

if (head != null) {
	let even = head.next;
	let even_head = head.next;
	let odd = head;
	while (even != null && even.next != null) {
		odd.next = odd.next.next;
		even.next = even.next.next;
		odd = odd.next;
		even = even.next;
	}
	odd.next = even_head;
}
return head;

whileの継続条件がポイント。行きすぎず余らせず走査を終わらせたい。evenが終端か終端一歩あと（null）にいけば終了とする（even == null or even.next == null)。oddは必ずevenの一歩手前にいるのでevenの終了条件だけで見ていれば良い。というわけでeven != null || even.next != null。

最後にoddのリストにevenのリストをつなげるが、この時evenはevenのリストの終端にいるのであらかじめ保存しておいたeven_headを繋げて完成。