# Coding Interviews: Simple Data Structures

Given the head of a singly linked list, reverse the list, and return *the reversed list*.

Given the heads of two singly linked-lists headA and headB, return *the node at which the two lists intersect*. If the two linked lists have no intersection at all, return null.

Given the head of a linked list and a value x, partition it such that all nodes **less than** x come before nodes **greater than or equal** to x.

You should **preserve** the original relative order of the nodes in each of the two partitions.

Given an integer array nums where the elements are sorted in **ascending order**, convert *it to a ***height-balanced ***binary search tree*.

Given the root of a binary tree, *determine if it is a valid binary search tree (BST)*.

A **valid BST** is defined as follows:

The left subtreeof a node contains only nodes with keys **less than** the node's key.

The right subtree of a node contains only nodes with keys **greater than** the node's key.

Both the left and right subtrees must also be binary search trees.

You are given the root of a binary search tree (BST), where the values of **exactly** two nodes of the tree were swapped by mistake. *Recover the tree without changing its structure*.

You are given two binary trees root1 and root2.

Imagine the trees are layed ontop of each other. The merged nodes will have the sum of the values of the original nodes. If one or the other is null, treat the null node as if it had a value of 0.

Return *the merged tree*.

You are given a **0-indexed** array of **unique** strings words.

A **palindrome pair** is a pair of integers (i, j) such that:

0 <= i, j < words.length,

i != j, and

words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return *an array of all the ***palindrome pairs*** of *words.

You must write an algorithm with O(sum of words[i].length) runtime complexity.

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. **Note that ****pos**** is not passed as a parameter**.

Return true* if there is a cycle in the linked list*. Otherwise, return false.

Given a 1-indexed integer array prices, where prices[i] is the price of a particular stock on the ith day, your task is to select some of the elements of prices such that your selection is linear.

A selection indexes, where indexes is a 1-indexed integer array of length k which is a subsequence of the array [1, 2, ..., n], is linear if:

For every 1 < j <= k, prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1]

The score of a linear selection is the sum of the prices at those indices, return the maximum score that a linear selection can have given the input.

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Given the head of a linked list, reverse the nodes of the list k at a time, and return *the modified list*.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Given the root of a binary tree, return *the inorder traversal of its nodes' values*.

Given the root of a binary tree and an integer targetSum, return true if the tree has a **root-to-leaf** path such that adding up all the values along the path equals targetSum.

A **leaf** is a node with no children.

Given an m x n board of characters and a list of strings words, return *all words on the board*.

Each word must be constructed from letters of sequentially adjacent cells, where **adjacent cells** are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Given a binary tree, determine if it is **height-balanced**.

Given the root of a binary tree, return *the length of the ***diameter*** of the tree*.

The **diameter** of a binary tree is the **length** of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The **length** of a path between two nodes is represented by the number of edges between them.

Given the root of a binary tree and an integer targetSum, return *the number of paths where the sum of the values along the path equals* targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).