みんな大好き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が得られます。
スポンサーリンク
コード
繰り返しの場合のコードになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/** * 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になった感じです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// 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); } } |
今回はシンプルでわかりやすかったですね。
