전단 면접 에서 흔히 볼 수 있 는 데이터 구조 문제

링크
1. 링크 에 고리 가 있 는 지 없 는 지 어떻게 판단 합 니까?
사고: 빠 르 고 느 린 지침, 하 나 는 빨리 가 고 하 나 는 느리게 간다. 그러면 몇 걸음 후에 빠 르 고 느 린 지침 이 만 날 것 이다.

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

var hasCycle = function(head) {
    if( head == null || head.next == null ){
        return false;
    }
    var slow = head; //slow pointer moves one step forward
    var fast = head; //fast pointer moves two steps forward
    while( true ){
        if( fast.next == null || fast.next.next == null ){
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
        if( fast === slow ){
            return true;
        }
    }
};

2. 링크 의 반전 (재 귀 법)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(head == null || head.next == null ) 
                return head;
            var nextNode = head.next;
            var newHead = reverseList(nextNode);
            nextNode.next = head;
            head.next = null;
            return newHead;
};

3. 링크 의 특정한 노드 삭제

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
          if (head == null) return null;
    var node = head;
    while(node != null && node.next != null){
        if(node.next.val == val){
            node.next = node.next.next;
        }
        else{
            node = node.next;
        }
    }

    return head.val == val ? head.next : head;
};

2. 창고 와 대열
1. 두 개의 스 택 으로 하나의 대기 열 을 실현 합 니 다.
우 리 는 현재 두 개의 스 택 이 있 는데, 하나의 직관 적 인 생각 은 데 이 터 를 두 개의 스 택 사이 에서 이동 시 켜 선진 적 인 목적 을 달성 할 수 있 도록 하 는 것 이다.이 두 스 택 이 스 택 A 와 스 택 B 라 고 가정 하면 스 택 A 는 enqueue 의 데 이 터 를 받 고 스 택 B 는 dequeue 데 이 터 를 사용 하 며 구체 적 인 알고리즘 은:
enqueue: (1) 스 택 A 에 데 이 터 를 직접 압축 합 니 다.
dequeue: (1) 스 택 B 가 비어 있 지 않 으 면 스 택 B 상단 의 데 이 터 를 팝 업 (2) 스 택 B 가 비어 있 으 면 스 택 A 의 모든 데 이 터 를 팝 업 하고 스 택 B 에 눌 러 서 스 택 B 상단 의 데 이 터 를 팝 업 합 니 다.
2. 두 개의 대기 열 로 스 택 실현
만약 에 우리 가 현재 대기 열 A 와 대기 열 B 가 있다 고 가정 하면 직관 적 이기 때문에 직접 알고리즘 에 올 라 갑 니 다.
push: (1) 요 소 를 대기 열 A 에 추가 합 니 다.
pop: (1) 대기 열 A 의 size 를 1 보다 클 때, 반복 적 으로 대기 열 A 의 요 소 를 대기 열 B (2) 로 이동 시 켜 대기 열 A 의 마지막 남 은 요 소 를 대기 열 에서 나 오고 결과 로 되 돌려 줍 니 다 (3) 대기 열 A 와 대기 열 B 의 이름 을 교환 합 니 다.