subtracting the linkedlist nodes

Question

I am trying to solve a linked list problem. Given a singly linked list, modify the value of first half nodes such that :

1st node’s new value = the last node’s value - first node’s current value

2nd node’s new value = the second last node’s value - 2nd node’s current value

Example :

Given linked list 1 -> 2 -> 3 -> 4 -> 5,

You should return 4 -> 2 -> 3 -> 4 -> 5

So far solution I could think of is

1. Iterate the linkedlist to find the length .
2. Iterate the second half of linked list to push the node values into a stack
3. Iterate the first half of list , pop the stack , subtract the node values.

Probably this is the most naive solution . Can annyone please suggest more efficient solution in terms of time/space (want to avoid multiple iterations and extra space for stack ) ? Thanks in advance.

Answer :

public ListNode subtract(ListNode a) {

        ListNode slow =a;
        ListNode fast=a;


        ListNode head = a;

        ListNode middle = null;

        while(fast!=null && fast.next!=null)
            {

                if(fast.next.next!=null) // in case numOfNodes are even , we need to stay at middle
                    slow=slow.next;
                fast = fast.next.next;

            }
       if(slow==fast)
            return a;

       middle = slow; 
       ListNode secondHalf = middle.next;
       middle.next = null;

       ListNode reversed = reverse(secondHalf);

       ListNode  temp1  = reversed;

       while(temp1!=null ){
           head.val = temp1.val - head.val;
           temp1 = temp1.next;
           head = head.next;
       }

       middle.next = reverse(reversed);


       return a;

    }


    public ListNode reverse(ListNode head){
        ListNode current = head;
        ListNode previous = null;

        while(current!=null) {
            ListNode temp = current.next;
            current.next = previous;
            previous = current;
            current = temp;

        }

        return previous;
    }

Answer 1

You can write a recursive function that will solve this problem without extra space i.e. if you do not consider the stack frame as extra space.

The code is written in C# but you should be able to easily translate it the the language you need.

One caveat with this approach is that you need to keep track of the current node we are on with a global variable.

static ListNode<int> temp = list.head; // Point to first element in the list
private static int reverse(ListNode<int> listNode, int currentNode, int totalNodes)
{
    if (listNode == null)
    {
        return 0;
    }
    currentNode = reverse(listNode.next, currentNode, totalNodes + 1);
    if (currentNode < totalNodes) //To check if half is reached
    {
        temp.data = listNode.data - temp.data;
        temp = temp.next;
    }
    return ++currentNode;
}

You can invoke this method as such reverse(list.head, 0, 0); and ignore the return value or store it somewhere as it points to the middle of the linked list which might come handy somewhere later on.

With the standard implementation of linked list I doubt if you will be able to achieve space/time complexity any better than this.

You can replace the global variable and pass it as an argument if you can modify the implementation of the ListNode to include the index of that node as well.

Answer 2

If you are allowed to modify the list then there is a better solution with constant extra space than the one I mentioned in the comments:

1. Find the middle.

2. Reverse the list from the middle to the right.

3. Perform the subtractions by going through the two lists step by step.

4. Reverse/join the lists back again to get the original list order.

All those steps require O(1) space and O(n) time, therefore the algorithm overall also requires O(1) space and O(n) time.

This is only an outline of the algorithm to prove that it is possible in O(n) time with constanst extra space, there are some traps like odd/even number of elements etc.

There might be some room for improvements, but you cannot get better than O(n) time, because finding the last element or performing the subtractions already requires O(n) time.