[LeetCodeやるお]206. Reverse Linked List

みんな大好きLeetCodeのお時間がやってまいりました。Reverse Linked Listについて学習したことをメモします。

これはクラッシックなインタビューの問題なのだそうです。

問題文は

Given the head of a singly linked list, reverse the list, and return the reversed list

と記載されています。Linked Listを反転させます。

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

とフォローアップに記載があり、繰り返し（iteratively）と再帰（recursively）で実装できるか？と記載されています。

アプローチ（繰り返し）

繰り返し（iteratively）のアプローチです。

最初はheadしか与えられていません。例えばhead = [1,2,3,4]だとすると
得なきゃ行けないものは[4,3,2,1]つまり4->3->2->1->nullです。

最初にprevノードとcurrノードを作成します。
ListNode prev = null;
ListNode curr = head;

次に繰り返しの中で、一時的なListNodeであるnextを宣言します。

while(curr!= null){
ListNode next = curr.next;

そこからの動きとしてはこんな感じです。
・currの次のリンクをprevを取得する（赤から青）
・prevを現在のノードにする（緑）
・currを次に進める（ピンク）

コードにすると

curr.next = prev;
prev = curr;
curr = next;

ですね。

これを最後まで進めていき、最終的にはcurrがnullに来たときにprevを返すことで4->3->2->1->nullが得られます。

スポンサーリンク

コード

繰り返しの場合のコードになります。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

// iterative
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while(curr!= null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

 

とってもシンプルでいいですね。再帰の場合もコンセプトは同じで、以下の通りになります。
先程のprevがnewHeadになった感じです。

// retcursive
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
    public ListNode reverse(ListNode head , ListNode newHead) {
        if(head == null){
        return newHead;
        } 
        
        ListNode next  = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
        return  reverse(head, newHead);
    }
    
}

今回はシンプルでわかりやすかったですね。