In most examples following class is used as node of linked list.

``````class ListNode(var `val`: Int=0) {
var next: ListNode? = null
}``````

## merge sorted lists

1. Straight way is to join lists into one then sort it by any sort algorithm.

2 . You can take first list as result, then insert nodes from other lists in appropriate position:

• search first element in result list which greater of the inserted element, and insert it before.
• if such element not found append to the end of result list
• when the inserted element is smaller than the head element, the inserted element becomes the new head

Complexity is O(kn), where k is number of lists. Memory complexity O(n) when you create new nodes, and O(1) when exists nodes are used.

Merge list in Kotlin

## detect cycle

1. Straight way is to make hash table and keep there a visited nodes. If node already in hash table, then list has cicle. Time complexity is O(n), memory complexity is O(n). There is variation of this metod, when node has flag, which we can use to mark visited nodes. In this case memory complexity is O(1).

Detect cycle with hash table

2. Floyd’s cycle-finding algorithm uses two nodes:

• create two nodes node1, node2 that point to the head of list
• traverse list from first node by one node, and from second node by two nodes
• traverse while node1, node2 nodes not equal to null and node2.next not equal to null
• if node1 equal to node2 while traversing then list have cycle

Time complexity is O(n), only one traversal of the loop is needed. Memory complexity is O(1).

Floyd’s cycle-finding algorithm

Let's digits of two numbers are stored in linked lists in revers order. Our task is to create a new linked list containing the sum of these numbers. There is no leading zero in the numbers (i.e. the last node does not contain a 0).