アルゴリズム_逆リンクリスト

Algorithem_ReverseLinkedList#

与えられた単方向リンクリストの先頭を逆転させ、逆転したリストを返します。

例 1:

入力: head = [1,2,3,4,5]
出力: [5,4,3,2,1]

例 2:

入力: head = [1,2]
出力: [2,1]

例 3:

入力: head = []
出力: []

制約:

リストのノード数は範囲 [0, 5000] です。
-5000 <= Node.val <= 5000

フォローアップ：リンクリストは反復的または再帰的に逆転できます。両方を実装できますか？

解法一#

フォローアップはさておき、最も直接的な解法は、LinkNode を配列に変換し、配列を逆順にしてから新しい LinkNode を生成することです。

コードは以下の通り：


/**
 * 単方向リンクリストの定義。
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        
        var newNode = head
        var nodeList: [Int] = []
        while newNode != nil {
            nodeList.append(newNode!.val)
            newNode = newNode?.next
        }
        
        var resultNode = ListNode(nodeList[nodeList.count - 1])
        var tempNode: ListNode?
        for i in 0...nodeList.count - 2 {
            let item = nodeList[nodeList.count - 2 - i]
            let generateNode = generateNewNode(item)
            if tempNode == nil {
                resultNode.next = generateNode
            }
            else {
                tempNode?.next = generateNode
            }
            tempNode = generateNode
        }
        
        return resultNode
    }
    
    func generateNewNode(_ val: Int) -> ListNode? {
        return ListNode(val)
    }
}

解法二#

ここは理解が難しいですが、Reverse a linked listを参考にしてください。ページの最下部にある動画を何度も見てください。

反復解法：

3 つのポインタを宣言します。prev = nil, current = head, next = nil,
LinkedList をループで遍歴します。
1. next を変更する前に、next を保存し、next = current.next を設定します。
2. 次に next を変更します。このステップが逆転の鍵です。current.next = prev を設定します。
3. その後、prev と current を次のノードに移動させ、prev = current, current = next を設定します。

コードは以下の通り：


/**
 * 単方向リンクリストの定義。
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var mutHead = head
        if mutHead == nil || mutHead?.next == nil {
            return mutHead
        }
        
        // 3つのポインタを初期化
        // prevをNULL、currをhead、nextをNULLとして
        var prev: ListNode?
        var curr = head
        var next: ListNode?
        
        // リンクリストを反復し、ループ内で次のことを行います
        while (curr != nil) {
            // 現在のnextを変更する前に
            // 次のノードを保存します
            next = curr?.next
            
            // 現在のnextを変更します
            // ここで逆転が起こります
            curr?.next = prev
            
            // prevとcurrを1ステップ前に進めます
            prev = curr
            curr = next
        }
        
        return prev
    }
}

解法三#

再帰解法：別の異なる理解、Reverse Linked List

重要なのは next ポインタの指向を変えることであり、異なる値を代入することではありません。

2 つの ListNode、prev と temp を宣言します。
prev は前のノードを表し、temp は一時的に保存するためのもので、mutHead が現在のもので、合計で 3 つの ListNode になります。
ループし、mutHead が空でない限り、
1. temp = mutHead、現在の値を temp に代入します。
2. mutHead = mutHead.next、mutHead を次のノードに代入します。
3. temp.next = prev、temp の next を prev に指向させます。この時点で temp の値は現在のものであり、現在の次は prev であり、ポインタの方向が逆転します。
4. prev = temp、prev を temp に代入し、次の反復に進み、mutHead が空になるまで続けます。

コードは以下の通り：


/**
 * 単方向リンクリストの定義。
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var mutHead = head
        if mutHead == nil || mutHead?.next == nil {
            return mutHead
        }
        
        var prev: ListNode?
        var temp: ListNode?
        while (mutHead != nil) {
            temp = mutHead
            mutHead = mutHead?.next
            temp?.next = prev
            prev = temp
        }

        return prev
    }
    
}

解法四#

再帰解法、参考 reclusive reverse linked list、
主に理解する必要があるのは：
再帰の中での各ステップで curr.next.next = curr と curr.next = nil の 2 つのステップです。


/**
 * 単方向リンクリストの定義。
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var mutHead = head
        if mutHead == nil || mutHead?.next == nil {
            return mutHead
        }
        
        // 再帰
        let newHead = reverseList(mutHead?.next)
        
        // 以下のコードは分けて見る必要があります
        // mutHead?.nextはmutHeadの次のListNodeを指します
        // mutHead?.next?.nextはmutHeadの次のListNodeのnextを指します
        // こうして逆指向が完成します
        mutHead?.next?.next = mutHead
        // その後、mutHead?.next、つまりmutHeadのnextをクリアします
        mutHead?.next = nil

        return newHead
    }
}