問題
与えられた単方向リストの最後からN番目の要素を求めよ.
該当の要素が無い場合はNULLを返却すること.
Solution
簡単に思いつく方法としては,
- 与えられたリストを最初から最後まで走査して, リストの長さを割り出す
- 後ろからN番目の要素は, リストの長さをMとすると先頭から
(N - M + 1)番目なので, 再度前からリストを走査する
があります.
algorithm_linkedlist_find_nth_from_tail_1.py
# Class of linked list Node.
class Node():
def __init__(self, val):
self.next = None
self.value = val
def next(self):
return self.next
def setNext(self, nextNode):
self.next = nextNode
def findElement(head, N):
if head == None:
return None
curNode = head
num = 1 # number of elements in list
while curNode.next:
num += 1
curNode = curNode.next
if num < N or N <= 0: # list is too short
return None
# get num - N + 1 node
curNode = head
curNum = 1
while curNum < num - N + 1:
curNum += 1
curNode = curNode.next
return curNode.value
計算量: O(M), 空間量: O(1)
algorithm_linkedlist_find_nth_from_tail_1.java
// Class of linked list node
class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
this.next = null;
}
public void setNext(Node nextNode) {
this.next = nextNode;
}
}
class Solution
{
public static Node findNthNodeFromTail(Node head, int N) {
if (head == null) return null;
int length = 1;
Node curNode = head;
while (curNode.next != null) {
length++;
curNode = curNode.next;
} // now length = length of the given list
if (length <= 0 || length < N) return null;
int curLength = 1;
curNode = head;
while (curLength < length - N + 1) {
curNode = curNode.next;
curLength++;
}
return curNode;
}
}
これも有向な方法ですが, リストを二回走査しています.
これを一回に減らそうと思うと, リストのノードを指すポインタを2つ用意して
- まず1つのポインタを先頭からN番目の要素まで進める
- もう1つのポインタを先頭に当てる
- 最初のポインタがtailに到達するまで, 両方のポインタを1つずつ進めていく
こうすると, 最後の状態として2つ目のポインタが後ろからN番目の要素で止まっていることになります.
algorithm_linkedlist_find_nth_from_tail_2.py
# Class of linked list Node.
def findElement(head, N):
if head == None:
return None
p1 = head
num = 1
while num < N:
num += 1
p1 = p1.next
if p1 is None:
return None
# get num - N + 1 node
p2 = head
while not p1.next is None:
p1 = p1.next
p2 = p2.next
return p2
計算量: O(M), 空間量: O(1)
algorithm_linkedlist_find_nth_from_tail_2.java
class Solution
{
public static Node findNthNodeFromTail(Node head, int N) {
if (head == null) return null;
int length = 1;
Node p1 = head;
while (length < N) {
length++;
p1 = p1.next;
if (p1 == null) return null;
} // now p1 is on the Nth node from the head
Node p2 = head;
while (p1.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
}
for分の繰り返しの数を考えると, リスト１巡り分しか走査していないことに注目です。ただし, 計算量のオーダーで考えると2MもMもO(M)なので, ２つの方法に差はありません。
このように, Linked listの問題では, 複数のポインタを用意して異なるペース, あるいは異なる出発点で各々を走査させることで, 問題を効率的に解くことが可能になることがあります.