[Refresh ! 코딩 테스트 / js] -61. Rotate List /

문제해석

• 연결리스트로 연결된 노드중. 다시 돌아오는 노드가 있니?

나의해석
1. 처음에 나는 하나를 고정하고 하나에 돌아오는 노드가 있는지 while문으로 돌렸다. 당연히 실패
예를 들면 3 일때 (head) while 문으로 돌면 당연히 계속 2 으로 돌아옴. x

해석

1. 사이클에 들어와라
2. 사이클에서 투포인터를 사용해라
3. 마치 예전에 초등시절에 배운 달리기 10km 달리는 사람과 20km 으로 달리는 사람은 겹치는 구간이 나오는가? 의 응용이라고 생각하면 쉽다...

코드

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    //투포인터 맞는데 하나를 두고 계속 진행해서 나한테 다시 돌아오면 true 아니면 false;
   
    //사이클에 들어왔다면 반드시 만난다
    let first=head;
    let second=head;
    while(second&&second.next){
        first=first.next;
        second=second.next.next;
        if(first==second) return true;
    }
   return false;

};

61. Rotate List

링크텍스트

문제해석
1. 회전을 얼마나 해야되는지 측정 k 에서 전체길이를 나눈다
2. 그럼 어디서 시작해야되는지를 알게됨
3. tail (맨끝과) head( 맨시작)을 연결
4. 여기서 중요한것은 2개의 pointer 가 더 필요함
5. 하나는 새로만들 node 의 시작점과 새로만들 node 의 앞 포인터
6. 왜냐하면 지금 circle 으로 연결해놨기때문에 회전을 끊어야됨

나의코드

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

   let tail=head;

   if (tail ==null) return null;

   while(tail.next){
    rotate_len+=1;
    tail=tail.next;
   }
   tail.next=head;
   
   let final_len= Math.floor(k%rotate_len);

   for(var i=0; i<rotate_len-final_len-1; i++){
    head=head.next;
   }
   let new_tail= head.next;
   head.next=null;
   return new_tail
  
 
};