Interview -- 算法实战

/**
 * @description 括号匹配
 * @param str str
 */
function matchBracket(str: string): boolean {
  const length = str.length
  if (length === 0) return true

  const stack = []

  const leftSymbols = '{[('
  const rightSymbols = '}])'

  for (let i = 0; i < length; i++) {
    const s = str[i]

    if (leftSymbols.includes(s)) {
      // 左括号, 压栈
      stack.push(s)
    } else if (rightSymbols.includes(s)) {
      // 左括号, 判断栈顶(是否出栈)
      const top = stack.pop()
      if (!isMatch(top, s)) return false
    }
  }

  return stack.length === 0
}

function isMatch(left: any, right: any): boolean {
  if (left === '(' && right === ')') return true
  if (left === '[' && right === ']') return true
  if (left === '{' && right === '}') return true
  return false
}

console.log(matchBracket('(a)'))

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
  // 节点少于 2 个
  if (head == null || head.next == null) return head

  let currentList = head,
    preList = null,
    nextList = null

  while (currentList.next !== null) {
    nextList = currentList.next
    currentList.next = preList
    preList = currentList
    currentList = nextList
  }
  currentList.next = preList

  return currentList
}