問題

与えられた単方向リストの最後から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の問題では, 複数のポインタを用意して異なるペース, あるいは異なる出発点で各々を走査させることで, 問題を効率的に解くことが可能になることがあります.