# Coding Interviews: Simple Data Structures

Given the head of a linked list, remove the nth node from the end of the list and return its head.

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one **sorted** list. The list should be made by splicing together the nodes of the first two lists.

Return *the head of the merged linked list*.

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

The "linked list" should be in the same order as a pre-order traversal of the binary tree.

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 root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should **not** change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a **unique answer**.

Return *the root of the trimmed binary search tree*. Note that the root may change depending on the given bounds.

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

Given the root of a binary tree, invert the tree, and return *its root*.

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

The LCA is defined as: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we **allow a node to be a descendant of itself**).”

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.

You are given two **non-empty** linked lists representing two non-negative integers. The digits are stored in **reverse order**, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Return the head of a deep copy of the list, ie all new nodes and both the node.next and node.random pointers point to new nodes.

Given the root of a binary tree, *check whether it is a mirror of itself* (i.e., symmetric around its center).

Given the root of a binary tree, return *the length of the longest path, where each node in the path has the same value*. This path may or may not pass through the root.

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

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

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

Given the head of a singly linked list, return true* if it is a palindrome or *false* otherwise*.