問題
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
https://leetcode.com/problems/merge-two-sorted-lists/
自分の解答
タイムアップ😊
コード理解
別解
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode newhead = new ListNode(0); ListNode curNode = newhead; while(l1!=null && l2!=null){ if(l1.val <= l2.val){ curNode.next = l1; l1 = l1.next; }else{ curNode.next = l2; l2 = l2.next; } curNode = curNode.next; } if(l1!=null){ curNode.next = l1; } if(l2 !=null){ curNode.next = l2; } return newhead.next; }
別解2
public ListNode mergeTwoLists1(ListNode l1, ListNode l2) { if (l1 == null && l2 == null) return null; if (l1 == null) return l2; if (l2 == null) return l1; ListNode test = new ListNode(0); ListNode result = test; if (l1.val >= l2.val) { result = l2; l2 = l2.next; result.next = mergeTwoLists(l1, l2); } else { result = l1; l1 = l1.next; result.next = mergeTwoLists(l1, l2); } return result; }
linkされているデータ構造なのでそれを活かしたロジックを書きたかったが撃沈。例えば
[1,2,7,8] [3,4,9,10]
がinputのとき、2のnext、4のnext、8のnextの3つの参照をかきかえるだけで本当はいけるはずだけど、そのロジックを書けず。そういう意味では別解は2つとも愚直にやっている。ただし別解1は最後のreturnをheader.nextで返せるようにダミーのheaderを作成してるアイデアがおもしろい。別解2は再帰。一瞬で書けたらクールだなと思う。疲れた。
今後のための考え方
- ダミーのデータを作って簡単に期待値をreturnできるようにするアイデアいいね
- Nodeはたどればリスト全体が見えるわけだから、Elementという認識ではなく、あるElement以降のList全てを指すという認識で考えると理解しやすい