.Zzumbong

[leetCode/JS] 876. Middle of the Linked List ๋ณธ๋ฌธ

coding test/leetCode

[leetCode/JS] 876. Middle of the Linked List

์ญ˜๋ด‰ 2022. 12. 5. 11:05

๋‚œ์ด๋„ [ ๐Ÿ˜Š ] Easy

๋ฌธ์ œ ์„ค๋ช…

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.

 

๋‹จ์ผ linked List ๋ฅผ ์ค€๋‹ค. list์˜ ์ค‘๊ฐ„ ๋ถ€ํ„ฐ returnํ•˜๋Š”๋ฐ, ์ค‘๊ฐ„์ด 2๊ฐœ ์ธ ๊ฒฝ์šฐ(์ง์ˆ˜ length) ์ผ๋•, 2๋ฒˆ์งธ ์ค‘๊ฐ„ ๊ฐ’ ๋ถ€ํ„ฐ return ํ•ด์ค€๋‹ค.

 

 

 

์ž…์ถœ๋ ฅ ์˜ˆ

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

 

 

 


 

 

๋‚ด ์†”๋ฃจ์…˜

  • ์—ฌ๋Ÿฌ ๋ฐฉ์‹์œผ๋กœ ํ’€๋˜ ์ค‘ list ์ž์ฒด๋ฅผ arr์— ๋„ฃ์–ด์„œ ์ค‘๊ฐ„ ๊ฐ’์ด ๋“ค์–ด์žˆ๋Š” ์š”์†Œ๋งŒ return ํ•˜๊ธฐ๋กœํ•จ.
/**
 * 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}
 */
// head = [1,2,3,4,5,6];
var middleNode = function(head) {
  const arr = [];
  let length = 0;
  let list = head;
  while(list) {
    length++;
    arr.push(list)
    list = list.next;
  }
  // arr = [ [1,2,3,4,5,6], [2,3,4,5,6], [3,4,5,6], [4,5,6], [5,6], [6] ]
  return arr[Math.floor(length/2)] // [4,5,6]
};

 

 

  const node = (list, fuc) => {
    if(!list) return;
    fuc(list);
    node(list.next, fuc);
  }
  node(head, (list) => {
    length++;
    arr.push(list)
  });

์ฒ˜์Œ์—” ์ˆœํšŒ๋ฅผ 2๋ฒˆํ•ด์„œ ์žฌ๊ท€์™€ function์„ param์œผ๋กœ ๋ณด๋‚ด์„œ ์ˆœํšŒ๋ฅผ ํ–ˆ์—ˆ๋‹ค.

 

์ตœ๊ณ ์˜ ์†”๋ฃจ์…˜

  • ์™€์šฐ.. ๊ฐœ๋˜‘๋˜‘์ด
  • fast.next.next๋กœ 2์นธ์”ฉ ๊ฑด๋„ˆ๋›ฐ์–ด์„œ ๋ฉˆ์ท„์„ ๋•Œ, slow๊ฐ€ ์ค‘๊ฐ„ node๊ฐ€ ๋œ๋‹ค.
var middleNode = function(head) {
    let slow = head;
    let fast = head;
    
    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

 

 

๊ฐ์ƒํ‰

  • linked list ๋ฌธ์ œ๋“ค์€ ์–ด๋–ป๊ฒŒ ์ˆœํšŒํ• ์ง€ ๊ณ ๋ฏผ์ด ๋˜์–ด ํ‘ธ๋Š” ์†๋„๊ฐ€ ๋А๋ ค์ง€๊ณคํ•œ๋‹ค.
  • list && list.next๋กœ while ๋Œ๋ฆฌ๋Š”๊ฒŒ ๊ฐ€์žฅ ์†ํŽธํ•œ ๋“ฏ.
  • ์ƒ๊ฐ๋ณด๋‹ค ๋นจ๋ž๋‹ค.

'coding test > leetCode' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[leetCode/JS] 938. Range Sum of BST  (0) 2022.12.07
[leetCode/JS] 328. Odd Even Linked List  (0) 2022.12.06
[leetCode/JS] 2256. Minimum Average Difference  (0) 2022.12.04
[leetCode/JS] 451. Sort Characters By Frequency  (0) 2022.12.03
[leetCode/JS] 1657. Determine if Two Strings Are Close  (0) 2022.12.02
Comments