LinkedList function from InterviewBit

Question

I'm struggling with my solution for a question on InterviewBit.

I linked to the full description, but in short:

1) You are given the head node of a linkedlist

2) take the first half of the list and change the values so 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"

Here is my approach (it compiles but does not mutate the list at all)

I see that my method does not actually modify the original list -- it seems like what I'm doing is making a new list with the correctly altered values, but not changing the original.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     public int val;
 *     public ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
public class Solution {
    public ListNode subtract(ListNode a) {
       ListNode current = a;
       int length = 0;

        //get length
        while(current.next != null){
            length++;
            current = current.next;
        }

        length += 1;

        while(current.next != null){

            double half = Math.floor(length/2);

            for(int i=0; i<half; i++ ){
                //
               // if(i == 0){
               //     int aval = (nthToLast(a, length)).val - a.val;
               //     a.val = ((nthToLast(a, length-i)).val - a.val);
               //     a.next = current;
               // }
                current.val = ((nthToLast(a, length-i)).val - current.val);
                current = current.next;
            }

        }
        return a;

    }

    /* Helper function that given LinkedList head, and int n, 
returns the nth to last ListNode in the LinkedList */

    public ListNode nthToLast(ListNode head, int n){
        ListNode nth = head;
        ListNode ahead = head; 

        /* strategy: set nth to head, and 'ahead' to n places in front of 'nth'
           increment at same speed and then when 'ahead' reaches the end, 'nth'
           will be in the nth place from the end.
        */

        while(ahead.next != null){
            for(int i=0; i<n; i++){
                ahead = ahead.next;
            }

            nth = nth.next;
            ahead = ahead.next;
        }

        return nth;
    }
}

Also -- I'm trying to get better at questions like these. Is this an ok approach for this question? I'd like to figure out how to make this work, but also if this is an all around bad approach please let me know.

Answer 1

break code into simple helper functions, make a function to get value of nth element in the linked list(this function is very easy to write) ,and then traverse the list upto the half every time calling that function to get the value of listSize-i member of the list and edit the value of the the ith member of the list. and make changes to the 1st few elements manually to check weather your linkList implementation is working or not

/**
 * Definition for singly-linked list.
 **/
class ListNode {
    public int val;
    public ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode subtract(ListNode a) {
        ListNode current = a;
        int length = 0;
        //get length
        while(current.next != null){
            length++;
            current = current.next;
        }
        length += 1;
        int half = length/2;
        //logic of this loop is 
        //go from 0 to half of the list
        // j goes from the last element to half
        //for example if size of list is 6 (indexing from 0)
        //when i is 0 j is 5
        //when i is 1 j is 4 and so on
        //so you get what you wanted
        for(int i=0,j=length-1; i<half; i++,j-- ){
            current.val=nthElement(a,j).val-current.val;
            current = current.next;
        }
        return a;
    }
    /* Helper function that given LinkedList head, and int n, 
    returns the nth node of LinkedList */
    public ListNode nthElement(ListNode head, int n){   //e.g-if n is 5 it will return the 5th node
        ListNode nth = head;
        for(int i=0; i<n; i++){
            nth = nth.next;
        }
        return nth;
    }
}