連結リストの走査で役立つランナーテクニックについてまとめる。

世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法で紹介されていて初めて知った。

ランナーテクニックとは

連結リストの先頭から走査していくポインタと、そのポインタより先から走査していくポインタの2種類を用意して、同時に走査していく方法。

これが何に役立つかというと、例えば次のような例題を解くのに役立つ。

例題

単方向連結リストの末尾からn番目の要素を見つけるアルゴリズムを実装しなさい。

package main

import "fmt"

type node struct {
	val  string
	next *node
}

type list struct {
	head *node
}

// 末尾からn番目のノードを探す
func (l *list) search(n int) *node {
	n1 := l.head
	n2 := l.head

       // n1はk番目のノードに設定
	for i := 0; i < n; i++ {
		if n1 == nil {
			return nil
		}
		n1 = n1.next
	}
        
　　　　　　　　// n2は先頭ノードから、n1はk番目のノードから走査する。
        // n1が末尾ノードに到達したらn2は末尾から数えてn番目のノードである。
	for n1 != nil {
		n1 = n1.next
		n2 = n2.next
	}

	return n2
}

func main() {
	l := &list{
		head: &node{
			val: "a",
			next: &node{
				val: "b",
				next: &node{
					val: "c",
					next: &node{
						val: "d",
					},
				},
			},
		},
	}
	fmt.Printf("%+v\n", l.search(1)) // d
	fmt.Printf("%+v\n", l.search(2)) // c
	fmt.Printf("%+v\n", l.search(3)) // b
	fmt.Printf("%+v\n", l.search(4)) // a
}

このようにランナーテクニックを使うと時間計算量はO（N）、空間計算量はO(1）で解くことができる。

連結リストのノード数が決まっていればわざわざポインタを２つ用意しなくとも、（全ノード数-n）が末尾からn番目となるので単純に解けるが、そうでない場合はこのように解くか、再帰で解くことになる。再帰の場合は計算量が増えるはず・・

所感

コーディングクイズで使えるシーンがありそうなので頭の片隅に留めておきたい。