LeetCode / Linked List / 876번 / Middle of Linked List / JS

< 문제 바로가기 >

Middle of the Linked List - LeetCode

 

< 문제 간단설명>

여러개의 노드로 연결된 linked list에서 중간 노드를 반환하면 되는 문제이다. 만약 노드의 개수가 짝수라면 중간 노드의 개수는 2개이므로 그 중 2번째 노드만 반환해준다.

 

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let list1 = head;
    let list2 = head;

    while(list2 && list2.next) {
        list1 = list1.next;
        list2 = list2.next.next;
    }

    return list1;
};

---

배열이라면 쉽게 할 수 있겠지만 Linked List 자료형이므로 인덱스로 접근이 불가하다.

따라서 주어진 head를 복사해서 한칸씩 next로 가는 Linked List 하나랑, 두칸씩 next로 가는 Linked List 하나를 선언해주었다. 따라서 list2가 두칸갈때 list1은 한칸을 가게되는데, 이는 list2가 마지막에 도착하게 된다면 결국 list1은 중간까지만 왔을것이다. 이를 이용해서 list1을 반환해주면 된다.