前提
エンジニア歴：3年
Java：1年
C#：2年
アルゴリズム、CSの専門知識無し
コーディングテストの為、学習中
問題
876. Middle of the Linked List
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
Constraints:
The number of nodes in the list is in the range [1, 100].
1 <= Node.val <= 100
解法
Node数を2で徐算した解に+1した要素が中央のノードになる。
/**
* 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; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode[] A = new ListNode[100];
int t = 0;
while (head != null){
A[t++] = head;
head = head.next;
}
return A[t / 2];
}
}
引っ掛かった所
1. ListNodeの理解不足
そもそもListNodeが何か理解していなかった。
少し調べてみたところ、このListNodeとはLinked List（連結リスト）と呼ばれるもので、「コンピュータサイエンスで使用される最も一般的なデータ構造の一つ」だそうです。
[引用元] ListNode (もしくはLinked Lists)
引数でListNodeクラスの配列が渡されると思っていたが、実際は連なったListNodeの先頭のインスタンスが渡される。
// 例題1の渡される引数
Input: head = [1,2,3,4,5]
// 渡されるListNodeのイメージです
ListNode{
int val = 1;
ListNode next = ListNode{
int val = 2;
ListNode next = ListNode{
int val = 3;
ListNode next = ListNode{
int val = 4;
ListNode next = ListNode{
int val = 5;
ListNode next = null;
}
}
}
}
}
2. インクリメントの理解不足
A[t++] = head;
インクリメントされて配列の要素を指定すると思っていたが、
実際にはtで配列の要素を指定してheadを代入後にインクリメントされる。
A[t] = head;
t = t + 1;
前置インクリメント演算子と後置インクリメント演算子の違いについて理解する必要があった。
[参考] 前置と後置の違い