I am solving a LeetCode Question to reverse nodes in K Group of a Linked List.

I have written the following program to reverse and its working fine.

package com.sample.testapp

class LinkedListPractice {
    class ListNode(val data: Int) {
        var next: ListNode? = null
    }
    companion object {
        @JvmStatic
        fun main(args: Array<String>) {

            var root: ListNode = ListNode(1)
            root.next = ListNode(2)
            root.next!!.next = ListNode(3)
            root.next!!.next?.next = ListNode(4)
            root.next!!.next?.next?.next = ListNode(5)
            println("Initial")
            prinLinkedList(root)

            var k = 2
            val answer = reverseKNodes(root, k)
            println()
            println("After reverse")
            prinLinkedList(answer)

        }

        fun prinLinkedList(root: ListNode?) {
            var current = root
            while (current != null) {
                print(current.data)
                current = current.next
                print("->")
            }
        }

        private fun reverseKNodes(root: ListNode?, k: Int): ListNode? {
            if (root == null) return null
            //reverse first k nodes and then call for next recursively until linkedlist ends
            var counter = 0
            var pre: ListNode? = null
            var next: ListNode? = null
            var current = root
            while (current != null && counter < k) {
                next = current?.next
                current?.next = pre
                pre = current
                current = next
                counter  
            }
            if (next != null) {
                root.next = reverseKNodes(next, k)
            }
            return pre
        }
    }
}

I am just confused in calculating Space Complexity for this program.

As per my understanding i am just creating pointers to nodes and reversing them so space complexity should be constant O(1), but i have a doubt that the ListNode pre and ListNode next are new and then value is assigned to them.

So as we are traversing all the K-Group a new pre node is created every time which we return. So should i call its space complexity as O(N) ?

Can somebody please help me clearing this doubt?

Any help will be appreciated.

CodePudding user response：

Space complexity estimates the size of (an abstract notion of) memory an algorithm needs to run, measured in terms of (a standard notion of) input size.

Your method implements a list reversal in chunks of k elements, k being a constant, ie. independent of the input size. Therefore, although you only handle single a single list node and its adjacency linkage at a time, your code is O(n), n being the list length, as you have floor(n/k) recursive calls each of which takes constant space on the stack.

Of course, you may bet on your compiler's optimizer to transform the tail recursion into a loop after which your code would indeed have space complexity O(1).

Note that very strictly speaking the memory requirement of a single pointer is not O(1) but O(log n) as no fixed pointer size could support an arbitrarily large linked list, but this consideration is typically abstracted away.

ListNode pre and ListNode next

These are only placeholders, ie represent a fixed amount of memory. While their content changes over the course of running the algorithm, the memory footprint does not.

CodePudding user response：

As per my understanding i am just creating pointers to nodes and reversing them so space complexity should be constant O(1)

It would be constant if there was no recursion. But every recursive execution context gets its own set of variables -- being the arguments root and k and the other locals counter, pre, next and current. As there are ceil(n/k) recursive calls happening, there are just as many of those six variables (which each take up a constant amount of memory), giving a space complexity of O(n/k).

I have a doubt that the ListNode pre and ListNode next are new and then value is assigned to them.

They are local variables. Using the word "new" here is a bit ambiguous, as we should not think of new instances of nodes. The only memory they take is for storing the object reference (pointer).

So as we are traversing all the K-Group a new pre node is created every time which we return.

No new nodes are created (there is no Node() constructor call in your code). The reference that is returned, is always an existing reference, which is used to overwrite the old reference in a next property.

So should I call its space complexity as O(N) ?

It is O(n/k)

To make it O(1), turn the recursion into a loop. This requires a few more variables:

    private fun reverseKNodes(root: ListNode?, k: Int): ListNode? {
        var counter = 0
        var pre: ListNode? = null
        var next: ListNode? = null
        var newRoot: ListNode? = null
        var tail: ListNode? = null
        var prevTail: ListNode? = null
        var current = root
        while (current != null) {
            tail = current
            counter = 0
            pre = null
            next = null
            while (current != null && counter < k) {
                next = current?.next
                current?.next = pre
                pre = current
                current = next
                counter  
            }
            if (newRoot == null) {
                newRoot = pre
            } else {
                prevTail?.next = pre
            }
            prevTail = tail
        }
        return newRoot
    }

Note that this is not the solution to the LeetCode challenge, since that code challenge stipulates:

If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

This is not what your code is doing. So you would need to add additional logic to look ahead and check there are still k nodes ahead before doing the actual reversal of a chunk.