3. Linkded List - Delete / Reverse

1. Linked List 삭제 (iterative / recursive)

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  append(val) {
    if(this.head === null) {
      this.head = new Node(val);
      return;
    }

    this._append(val, this.head)
  }

  _append(val, curr) {
    if(curr.next === null) {
      curr.next = new Node(val);
      return;
    }

    this._append(val, curr.next); 
  }

  print() {
    const output = this._print(this.head);
    console.log(output);
  }

  _print(curr) {
    if(curr === null) return '';
    return curr.val + this._print(curr.next);
  }

  contains(target) {
    return this._contains(target, this.head); 
  }

  _contains(target, curr) {
    if(curr === null) return false;
    if(curr.val === target) return true;
    return this._contains(target, curr.next);
  }
  
  // delete as iterateive
  deleteValue(target) {
    if(this.head.val === target) {
      this.head = this.head.next;
    }
    
    let prev = null;
    let curr = this.head;
    
    while(curr !== null) {
      if(curr.val === target) {
        prev.next = curr.next;
      }
      prev = curr;
      curr = curr.next;
    }
  } // O(n) time O(1) space
  
  // delete as recursive
  deleteValue(target) {
    if(this.head.val === target) {
      this.head = this.head.next;
      return;
    }
    
    this._deleteValue(this.head, null, target)
  }
  
  _deleteValue(curr, prev, target) {
    if(curr === null) {
      return;
    }
    
    if(curr.val === target) {
      prev.next = curr.next;
      return;
    }
    
    this._deleteValue(curr.next, curr, target);
  } // O(n) time O(n) space
}

const list = new LinkedList();

list.append('a')
list.append('b')
list.append('c')
list.append('d')
list.deleteValue('a')
console.log(list.print());

2. Linked List Reverse (iterative / recursive)

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }
  append(val) {
    if(this.head === null) {
      this.head = new Node(val)
      return;
    }
    let curr = this.head;
    while(curr.next !== null) {
      curr = curr.next;
    }
    curr.next = new Node(val) 
  }

  print() {
    let str = '';
    let curr = this.head;
    console.log(curr);
    while (curr !== null) {
      str += curr.val
      curr = curr.next;
    }
    return str
  }
 
  // reverseList as iterative
  reverseList() {
    let prev = null;
    let curr = this.head;

    while (curr !== null) {
      const next = curr.next;
      curr.next = prev;

      prev = curr;
      curr = next;
    }

    this.head = prev;
  }

  // reverseList as recursive
  reverseList() {
    if(this.head === null) {
      return;
    }
    this._reverseList(this.head)
  }

  _reverseList(curr, prev = null) {
    if (curr === null) {
      this.head = prev;
      return;
    }

    const next = curr.next;
    curr.next = prev;
    this._reverseList(next, curr);
  }
}

const list = new LinkedList();
list.append('a')
list.append('b')
list.append('c')
list.append('d')
list.reverseList()
console.log(list.print());

참고 : codebyte - Reverse a Linked List