備忘録集 LeetCode234. Palindrome Linked List

立地

自分用の備忘録

3行まとめ

• 与えられた連結リスト(Linked List)が回文になっているかどうかを返す。
• 連結リストを逆にたどることができれば(破壊的変更)、空間使用量もO(1)で可能

前提

Linked Listの定義

type ListNode struct {
	Val  int
	Next *ListNode
}

連結リストでfor文

// head := *ListNode
for node:=head;node!=nil;node=node.Next{}

実装

スライスに直した後、両端から順に比較

• time:O(n),space:O(n)
• 破壊的変更無し

func isPalindrome(head *ListNode) bool {
	sl := make([]int, 0)

	for node := head; node != nil; node = node.Next {
		sl = append(sl, node.Val)

	}

	len := len(sl)
	for i := 0; i < len/2; i++ {
		if sl[i] != sl[len-1-i] {
			return false
		}
	}
	return true
}

連結リストのまま

• time:O(n),space:O(1)
• 破壊的変更あり

1. headからstep1xは1つずつ、step2xは2つずつ進む。
2. step2xがnilに到達した時、step1xは連結リストの後半の最初の要素にある。
3. step1x以降を反転させて、tailを得る。(破壊的変更)
4. headとtailを比較する。

1.のループの回数が連結リストの長さ半分になっている。

func reverse(head *ListNode) *ListNode {
	cur, prev := head, (*ListNode)(nil)

	for cur != nil {
		next := cur.Next
		cur.Next = prev

		prev = cur
		cur = next
	}
	return prev

}
func isPalindrome2(head *ListNode) bool {
	// sl := make([]int, 0)
	half := 0
	step2x, step1x := head, head
	for ; step2x != nil && step2x.Next != nil; step2x, step1x = step2x.Next.Next, step1x.Next {
		half++
	}

	tail := reverse(step1x)

	for i, headside, tailside := 0, head, tail; i < half; i++ {
		if headside.Val != tailside.Val {
			return false
		}
		headside, tailside = headside.Next, tailside.Next
	}

	return true
}

破壊前後

記憶

• LeetCodeは関数レベルで問題がでてるのでテストが書きやすい。
• sliceToLinkedListの実装にミスがあってテスト通ってるのにバグってた

Link

https://github.com/oksongh/LeetCode/blob/main/234/main.go