CareerCup

Take two pointers. Point out from start. Move one pointer (say p) with one difference and another one (say q) with two difference. So when p is at n/2, q will be on n-1.
eg. n=10.
initially p=q=1.
now p=2 and q=3.
then p=3 and q=5.
then p=4 and q=7.
then p=5 and q=9.
Our search completes when q has no node to move or null.

I think what you mean by second last (n-1) node is where the * is

*                               n-1             n
_               _               _               _

{
p = ll.head; q == null; i = 0;
while (i < 3 && p != null) {
    p = p.next;
}

if (p != null) {
    q = ll.head;
}
while (p != null) {
  p = p.next;
  q = q.next;
}
//  q is your answer

}

The same principal applies to the second question. q advances half the distance of p in each loop. If p hits the end of the list before it could double its stride, then q advances half the different between end of list and p

to get any node from the last :first move a pointer that steps from start and after that take second pointer from start and move both pointer together until first reach at the end ..
now the second pointer points to the desire element from last

import java.util.ArrayList;

class NodeForGetSecondLastAndHalfNode {
    public int data;
    public NodeForGetSecondLastAndHalfNode next;

    public NodeForGetSecondLastAndHalfNode(int iData) {
        data = iData;
    }

    public void display() {
        System.out.print(data + " ==> ");
    }
}

class ListForGetSecondLastAndHalfNode {

    private NodeForGetSecondLastAndHalfNode first;

    public ListForGetSecondLastAndHalfNode() {
        first = null;
    }

    public boolean isEmpty() {
        if (first == null) {
            return true;
        }
        return false;
    }

    public void insertData(int data) {
        System.out.println("INSERT: " + data);
        NodeForGetSecondLastAndHalfNode newElm = new NodeForGetSecondLastAndHalfNode(data);
        newElm.next = first;
        first = newElm;
    }

    public void display() {
        System.out.println("DISPLAY");
        if (isEmpty()) {
            System.out.println("EMPTY");
            return;
        }
        NodeForGetSecondLastAndHalfNode curr = first;
        while (curr != null) {
            curr.display();
            curr = curr.next;
        }
        System.out.println();
    }

    public NodeForGetSecondLastAndHalfNode getFirst() {
        if (isEmpty()) {
            return null;
        }
        return first;
    }
}

class GetSecondLastAndHalfNodeSolution {

    public Object getSecondLastNode(ListForGetSecondLastAndHalfNode list) {
        list.display();
        System.out.print("\t SECOND LAST NODE: ");
        NodeForGetSecondLastAndHalfNode slow = list.getFirst();
        if (list.isEmpty()) {
            return null;
        } else if (slow.next == null) {
            return null;
        }
        NodeForGetSecondLastAndHalfNode fast = slow.next;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        System.out.println(slow.data);
        return slow;
    }

    public ArrayList<Integer> getHalfNode(ListForGetSecondLastAndHalfNode list) {
        list.display();
        NodeForGetSecondLastAndHalfNode slow = list.getFirst();
        System.out.print("\t MID NODES: ");
        ArrayList<Integer> out = new ArrayList<Integer>();
        if (list.isEmpty()) {
            return out;
        } else if (slow.next == null || slow.next.next == null) {
            out.add(slow.data);
        } else {
            NodeForGetSecondLastAndHalfNode fast = slow.next;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            if (fast != null) {
                out.add(slow.data);
                out.add(slow.next.data);
            } else {
                out.add(slow.data);
            }
        }
        return out;
    }

    public void display(ArrayList<Integer> out) {
        for (int i = 0; i < out.size(); i++) {
            System.out.print(out.get(i) + " , ");
        }
        System.out.println();
    }
}

square of n is n times n which is n+n+n+... n-times
so simplest solution for this is ...

int getSqareOfNWithPlusOperator(int n) {
int squareOfN = 0;
for (int I = 0 ; I < n; I++) {
	squareOfN += n;
}

return squareOfN;
}

class ListNode(object):
	def __init__(self, x):
		self.val = x
		self.next = None

def search(node, target_distance):
	if node is None:
		return -1, None

	distance, target_node = search(node.next, target_distance)
	if distance + 1 == target_distance:
		target_node = node
	return distance + 1, target_node

if __name__ == '__main__':
	data = '1234567890'

	seed = None
	last_node = None
	for d in data:
		node = ListNode(d)
		if seed is None:
			seed = node
		if last_node is not None:
			last_node.next = node
		last_node = node

	distance, target_node = search(seed, 0)
	print target_node.val

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

def search(node, target_distance):
if node is None:
return -1, None

distance, target_node = search(node.next, target_distance)
if distance + 1 == target_distance:
target_node = node
return distance + 1, target_node

if __name__ == '__main__':
data = '1234567890'

seed = None
last_node = None
for d in data:
node = ListNode(d)
if seed is None:
seed = node
if last_node is not None:
last_node.next = node
last_node = node

distance, target_node = search(seed, 0)
print target_node.val

public LinkedListNode nthToLastLessComplexity(int n) { //is the value of nth node from last
		if(head== null){
			return null;
		}
		LinkedListNode currentNode = head;
		int length = 0;
		while(currentNode!=null){
			currentNode = currentNode.getNext();
			length ++;
		}
		int m = length;
		int val = m-n+1;
		currentNode = head;
		for(int i=1;i<val;i++){
			currentNode = currentNode.getNext();
		}
	
		return currentNode;
		//complexity is O(n)
	}