Linked List Cycle

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

Example

Given -21->10->4->5, tail connects to node index 1, return true

Challenge

Can you solve it without using extra space?

Reorder List

Given a singly linked list L: L0→L1→…→L(n-1)→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→L(n-2)→…

You must do this in-place without altering the nodes’ values.

Example

Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example

Given 1-3->2->null, sort it to 1->2->3->null.

Merge Two Sorted Lists

Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splicing together the nodes of the two lists and sorted in ascending order.

Example

Given 1->3->8->11->15->null, 2->null , return 1->2->3->8->11->15->null.

Remove Nth Node from End of List

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

Example

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

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

Note

The minimum number of nodes in list is n.

Challenge

O(n) time

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Example

Given 4 gas stations with gas[i]=[1,1,3,1], and the cost[i]=[2,2,1,1]. The starting gas station’s index is 2.

Note

The solution is guaranteed to be unique.

Challenge

O(n) time and O(1) extra space

Majority Number Show result

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

Example

Given [1, 20, 23, 4, 8], the largest formed number is 8423201.

Note

The result may be very large, so you need to return a string instead of an integer.

Challenge

Do it in O(nlogn) time complexity.

You must follow the order:

1
2

in qemu/
make distclean

1
2

in rom/
make bios CONFIG_ROM_SIZE=256

1
2

in qemu/
./configure --target-list=x86_64-softmmu

1
2
3

in qemu/
make
make install

Delete Digits

Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

Find the smallest integer after remove k digits.

N <= 240 and k <= N,

Example

Given an integer A = “178542”, k = 4

return a string “12”