It's the Xinrui Ma

# Blog

## Given a singly linked list, determine if it is a palindrome.

Posted by in LeetCode on

Given a singly linked list, determine if it is a palindrome.

Example 1:

```Input: 1->2
Output: false```

Example 2:

```Input: 1->2->2->1
Output: true```

Could you do it in O(n) time and O(1) space?

Solution:
1.get the length of the link list.
2. get the second half of the linked list
3. reverse the second half of linked list
4. compare beginning of list and the reversed second half, until reversed equals null

## Binary tree preorder, inorder, postorder traverse iteratively in JavaScript

Posted by in LeetCode on

preOrder:

Inorder:

Postorder:

Posted by in LeetCode on

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

```Input: `1->2->3->4->5->NULL`
Output: `1->3->5->2->4->NULL````

Example 2:

```Input: 2`->1->3->5->6->4->7->NULL`
Output: `2->3->6->7->1->5->4->NULL````

Note:

• The relative order inside both the even and odd groups should remain as it was in the input.
• The first node is considered odd, the second node even and so on …

Solution:
Draw an example, record the original even node, set two points which are start even node and odd node, change their next accodringly.

Posted by in LeetCode on

Remove all elements from a linked list of integers that have value val.

Example:

```Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5```

Solution:

Posted by in LeetCode on

Example:

```Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL```

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution:

## Remove Nth Node From End of List

Posted by in LeetCode on

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

Example:

```Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.```

Note:

Given n will always be valid.

Could you do this in one pass?

Solution:

## Linked List Cycle II Go to Discuss

Posted by in LeetCode on

Given a linked list, return the node where the cycle begins. If there is no cycle, return `null`.

Note: Do not modify the linked list.

Can you solve it without using extra space?

Solution in JavaScript:

## Design Linked List in JavaScript

Posted by in LeetCode on

Design your implementation of the linked list. You can choose to use the singly linked list or the doubly linked list. A node in a singly linked list should have two attributes: `val` and `next`. `val` is the value of the current node, and `next` is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute `prev` to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

• get(index) : Get the value of the `index`-th node in the linked list. If the index is invalid, return `-1`.
• addAtHead(val) : Add a node of value `val` before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
• addAtTail(val) : Append a node of value `val` to the last element of the linked list.
• addAtIndex(index, val) : Add a node of value `val` before the `index`-th node in the linked list. If `index` equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
• deleteAtIndex(index) : Delete the `index`-th node in the linked list, if the index is valid.

Example:

```MyLinkedList linkedList = new MyLinkedList();

Note:

• All values will be in the range of `[1, 1000]`.
• The number of operations will be in the range of `[1, 1000]`.

Solution:

## Kth Largest Element in a Stream

Posted by in LeetCode on

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your `KthLargest` class will have a constructor which accepts an integer `k` and an integer array `nums`, which contains initial elements from the stream. For each call to the method `KthLargest.add`, return the element representing the kth largest element in the stream.

Example:

```int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);

Note:
You may assume that `nums`‘ length ≥ `k-1` and `k` ≥ 1.

Solution:

Correct One:

## Delete Node in a BST

Posted by in LeetCode on

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

```root = [5,3,6,2,4,null,7]
key = 3

5
/ \
3   6
/ \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

5
/ \
4   6
/     \
2       7

5
/ \
2   6
\   \
4   7```

Solution:
1. So if we delete the node is the leaf, we just set the node to null
2. If the node deleted only have one child, let’s say, only left child exist, so set root = root.left;
3. If the node deleted have two children, we first find it’s left most child in it’s right subtree. Called Successor.
4. Then we swap the tree node, trick here is we just change the value of the node, and we delete the successor in root’s right subtree
5. If the node value large than key, means we only need to consern root’s left subtree. root.left = deleteNode(root.left, key)