[JS]알고리즘 문제풀이 8_linked list활용

linked list에 대한 개념 정리와 기본적인 메소드를 정의한 알고리즘 문제

/*
 * Implement a linked list using the pseudoclassical instantiation pattern.
 *
 * Your linked list should have methods called "addToTail", "removeHead", and "contains."
 *
 */
 
// EXAMPLE USAGE:
// var list = new LinkedList();
// list.tail;         //yields 'null'
// list.addToTail(4);
// list.addToTail(5);
// list.head.value;   //yields '4';
// list.contains(5);  //yields 'true';
// list.contains(6);  //yields 'false';
// list.removeHead(); //yields '4'
// list.tail.value;   //yields '5';
 
 
var LinkedList = function(){
  this.length = 0
  this.head = null
  this.tail = null
};
 
//write methods here!
 
LinkedList.prototype.addToTail = function(value){
  let newNode = new this.makeNode(value)
  let oldTail = this.tail;
  if(!this.head){
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail = newNode;
    oldTail.next = this.tail;
  }
  this.length ++;
};
 
LinkedList.prototype.removeHead = function(){
  if(!this.head.next){
    this.head = null;
    this.tail = null;
  } else {
    this.head = this.head.next;
  }
  this.length --;
};
 
LinkedList.prototype.contains = function(value){
  let curr = this.head
  //let pre = this.head.next
  while(curr){
    if(curr.value === value){
      return true;
    } 
    curr = curr.next
    //pre = pre.next
  }
  return false;
};
 
LinkedList.prototype.makeNode = function(value){
  this.value = value;
  this.next = null;
  return this;
};
 

 

그리고 위의 연결리스트에 대한 개념을 심화하여, 해당 연결리스트가 순환하는지 아니면, 마지막이 null로 끝나는지를 점검

www.zerocho.com/category/Algorithm/post/58008a628475ed00152d6c4d

(Algorithm) 자료구조(연결 리스트, linked list)

위의 블로그를 참고하면, 이중연결리스트인지 여부를 점검하는 것이다.

제일 마지막 노드의 next가 리스트 중 하나의 노드로 이어지는 것이다.

연결리스트에 대한 개념은 차후에 정리해보겠다.

/*
 * Assignment: Write a function that returns true if a linked list contains a cycle, or false if it terminates somewhere
 *
 * Explanation:
 *
 * Generally, we assume that a linked list will terminate in a null next pointer, as follows:
 *
 * A -> B -> C -> D -> E -> null
 *
 * A 'cycle' in a linked list is when traversing the list would result in visiting the same nodes over and over
 * This is caused by pointing a node in the list to another node that already appeared earlier in the list. Example:
 *
 * A -> B -> C
 *      ^    |
 *      |    v
 *      E <- D
 *
 * Example code:
 *
 * var nodeA = Node('A');
 * var nodeB = nodeA.next = Node('B');
 * var nodeC = nodeB.next = Node('C');
 * var nodeD = nodeC.next = Node('D');
 * var nodeE = nodeD.next = Node('E');
 * hasCycle(nodeA); // => false
 * nodeE.next = nodeB;
 * hasCycle(nodeA); // => true
 *
 * Constraint 1: Do this in linear time
 * Constraint 2: Do this in constant space
 * Constraint 3: Do not mutate the original nodes in any way
 */
// cycle 인 경우!
// 1차
// A (s,f)-> B -> C
//           |    |
//           E <- D
// 2차
// A-> B(s) -> C(f)
//      |        |
//      E   <-   D
 
// 3차
// A->  B   ->  C(s)
//      |        |
//      E (f) <- D
 
// 4차
// A->  B   ->  C(f)
//      |        |
//      E   <- D(s)
 
// 5차
// A->  B     ->  C
//      |         |
//      E (s,f)<- D
 
// cycle이 아닌경우!
// 1차
// A (s,f)-> B -> C -> D -> E -> null
 
// 2차
// A -> B(s) -> C(f) -> D -> E -> null
 
// 3차
// A -> B -> C(s) -> D -> E(f) -> null
 
// 4차
// A->  B  -> C -> D(s) -> E -> null => checkFast 말은 연결리스트를 벗어나서 null이 되어버림
 
var Node = function (value) {
  return { value: value, next: null };
};
 
var hasCycle = function (linkedList) {
  //해당 함수의 인자로 연결리스트의 노드 중 하나가 주어졌을 때, 이중연결인지 아닌지의 여부를 점검
  //https://medium.com/@joshuablankenshipnola/checking-for-linked-list-cycles-in-javascript-77ec9adc6822
  //연결리스트를 순회하는 두개의 말이 있다고 가정,
  //하나는 한칸씩 이동하고, 나머지 하나는 두칸씩 이동한다. 그러다가 이 두개의 말이 어디선가 만나게 된다면 이는 이중 연결 리스트라는 의미이다.
  let checkSlow = linkedList;
  let checkFast = linkedList;
  while (checkFast && checkFast.next) {
    checkSlow = checkSlow.next;
    checkFast = checkFast.next.next;
    if (checkSlow === checkFast) {
      return true;
    }
  }
  return false;
};
 

 

Reference

medium.com/@joshuablankenshipnola/checking-for-linked-list-cycles-in-javascript-77ec9adc6822

Checking For Linked List Cycles in JavaScript