It's the Xinrui Ma

# Blog

Posted by in LeetCode on

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 contain a single digit. Add the two numbers and return it as a linked list.

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

Example

```Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.```

Solution:
Easy, but need to watch out for the last carry;

## merge two sorted linked list Iteratively and Recursively

Posted by in LeetCode on

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

```Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4```

Recursively:

Iteratively:

## 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

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:

## Reverse a singly linked list.

Posted by in LeetCode on