# Removing Elements

Give you an array num and a value val. you need to remove all elements with a value equal to Val in place and return the new length of the removed array.

Instead of using extra array space, you must use only O(1) extra space and modify the input array in place.

The order of elements can be changed. You don't need to consider the elements in the array that exceed the new length.

Example 1: given num = [3,2,2,3], Val = 3, the function should return a new length of 2, and the first two elements in num are 2. You don't need to consider the elements in the array that exceed the new length.

Example 2: given num = [0,1,2,2,3,0,4,2], Val = 2, the function should return a new length of 5, and the first five elements in num are 0, 1, 3, 0, 4.

You don't need to consider the elements in the array that exceed the new length.

def solution(nums, val): slow = 0 fast = 0 n = len(nums) while fast < n: if nums[fast] != val: nums[slow] = nums[fast] slow += 1 fast += 1 return slow

# Reverse string

Write a function that inverts the input string. The input string is given in the form of character array char [].

Do not allocate additional space to another array. You must modify the input array in place and use the additional space of O(1) to solve this problem.

You can assume that all characters in the array are printable characters in the ASCII code table.

Example 1:

Input: ["h", "e", "l", "l", "o"]

Output: ["o", "l", "l", "e", "h"]

Example 2:

Input: [H "," a "," n "," n "," a "," H "]

Output: ["H", "a", "n", "n", "a", "H"]

def solution(strs): left = 0 right = len(strs) - 1 while left < right: strs[left], str[right] = strs[right], strs[left] left += 1 right -= 1

# Sword finger Offer 05. Replace spaces

Please implement a function to replace each space in the string s with "% 20".

Example 1: Enter: s = "We are happy."

Output: "We%20are%20happy."

def solution(strs): counts = strs.count(" ") res = list(strs) res.extend([" "] * counts*2) left, right = len(strs)-1, len(res)-1 while left >= 0: if res[left] != " ": res[right] = res[left] right -= 1 else: res[right-2:right+1] = "%20" right -= 3 left -= 1 return "".join(res)

# Reverse linked list

Reverse a single linked list.

Example: input: 1 - > 2 - > 3 - > 4 - > 5 - > null output: 5 - > 4 - > 3 - > 2 - > 1 - > null

def solution(head): pre = None cur = head while cur: tmp = cur.next cur.next = pre pre = cur cur = tmp return pre

# Linked list intersection

Given two (one-way) linked lists, determine whether they intersect and return the intersection. Note that the definition of intersection is based on the reference of the node, not the value of the node. In other words, if the k-th node of a linked list and the j-th node of another linked list are the same node (the references are exactly the same), the two linked lists intersect.

Example 1:

Input: listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]

Output: Reference of the node with value = 8

Input explanation: the value of intersection node is 8 (note that if two lists intersect, it cannot be 0). Starting from their respective headers, linked list A is [4,1,8,4,5], and linked list B is [5,0,1,8,4,5]. In A, there are 2 nodes before the intersection node; In B, there are 3 nodes before the intersection node.

def solution(heada, headb): prea = heada preb = headb while prea != preb: if prea.next: prea = prea.next else: prea = preb if preb.next: preb = preb.next else: preb = prea return prea

# Circular linked list II

Given a linked list, return the first node from the linked list into the ring. If the linked list is acyclic, null is returned.

In order to represent the rings in a given linked list, the integer pos is used to represent the position where the tail of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there is no ring in the linked list.

Note: it is not allowed to modify the given linked list.

def solution(head): fast = head slow = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: p = head q = slow while p != q: p = p.next q = q.next return p return None

# Delete the penultimate node of the linked list

Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list.

Advanced: can you try using one scan?

def solution(head, n): pre = ListNode(0) pre.next = head slow, fast = pre, pre for _ in range(n): fast = fast.next while fast.next: slow = slow.next fast = fast.next slow.next = slow.next.next return pre.next