Linked lists algorithms

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.

fun ListNode.insertOrdered(ins: ListNode ): ListNode {
   var p : ListNode? = null // previous element
   var c : ListNode? = this // current element
    
   while(c != null)  { 
     if(ins.`val` < c.`val`){
        p?.also{
            it.next = ins
        }
        ins.next = c
        return if(p!=null) this else ins
     } 
   
     p = c
     c = c.next
   }
   
    p?.next = ins
    ins.next= null
    return this
}

fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    var ret :ListNode? = null
    var startIndex = 0
        
    for(i in 0 until lists.size){
        if(lists[i] != null){
            ret = lists[i]
            startIndex = i+1
            break
        }
    }
             
          
    if(ret==null) {
        return null
    }    
      
    for( i in startIndex until lists.size){
        var append = lists[i]
            
        while(append!=null){ 
            val n = append.next  
            ret = ret!!.insertOrdered(append)
            append = n
        }        
    }
            
    return ret
}

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).

    fun hasCycle(head: ListNode?): Boolean {
    val posMap = mutableMapOf <ListNode, Int> ()  
    var curIndex = 0
        
    var current = head  
      
    while(current!=null) {
        if(posMap[current] == null){
            posMap[current]=curIndex++
            current = current.next
        }else {
            return true
        }
    } 
        
    return false 
}

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).

fun hasCycle(head: ListNode?): Boolean {
            
    var node1 : ListNode? = head  
    var node2 : ListNode? = head
              
    while(node1!=null && node2!=null && node2.next!=null){
      
        node1 = node1.next
        node2 = node2?.next?.next
        
        if(node1 == node2){
            return true
        }
    }
       
    return false
}

add two numbers

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).

fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
    
    val ret = ListNode(0)
        
    var curDigit = ret
    var prevDigit : ListNode? = null
    var num1 = l1
    var num2 = l2
        
    while(num1!=null || num2!=null){
        val sum = (num1?.`val` ?:0) + (num2?.`val` ?: 0) + curDigit.`val`
            
        curDigit.`val` = sum.rem(10)
          
        num1 = num1?.next
        num2 = num2?.next
        prevDigit = curDigit
            
        curDigit.next = ListNode(if(sum >= 10) 1 else 0)
        }
            
        curDigit = curDigit.next            
    }
        
        
    if(curDigit.`val` == 0){
        prevDigit?.next = null
    }
        
    return ret
}

add two numbers 2

Let's digits of two numbers are stored in linked lists (unlike previous not in reverse 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 first node does not contain a 0). To change input lists is not allowed.

1. You can save digits in stacks, i.e. inverse order of digits. Then calculate the sum in the same way as in the previous task.

fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
    when{
        l1==null && l2==null -> return null
        l1!=null && l2==null -> return l1
        l1==null && l2!=null -> return l2
    }
        
        
    var stack1 = ArrayDeque<Int>()
    var stack2 = ArrayDeque<Int>()
        
    var num1 = l1
    var num2 = l2
        
    var a = 0
    var b = 0
    var carry = 0
    var sum = 0
        
    var ret = ListNode(0)
        
    while(num1!=null){
        stack1.push(num1.`val`)
        num1 = num1.next
    }
        
    while(num2!=null){
        stack2.push(num2.`val`)
        num2 = num2.next
    }
                
    while(!stack1.isEmpty() || !stack2.isEmpty()){
            
        a = 0
        b = 0
        carry = ret.`val`
            
        if(!stack1.isEmpty())
            a = stack1.pop()
                        
        if(!stack2.isEmpty())
             b = stack2.pop()
            
        sum = a + b +carry
            
        ret.`val` = sum.rem(10)
        carry = sum / 10
            
        ret = ListNode(carry).apply{next=ret}           
    }
        
    // remove leading 0    
    if(ret.`val` ==0 ){
        ret = ret.next
    }
        
    return ret
}

reverse

fun reverseList(head: ListNode?): ListNode? {
       
    var prev : ListNode? = null
    var current : ListNode? = head
    var tmpNext : ListNode? = null
        
    while(current !=null){
        tmpNext = current.next
            
        current.next = prev
        prev = current
        current = tmpNext
    }
        
    return prev
}