Interview Question Software Engineer / Developers
Country: United States
Hi
I assume that it is a single linked list.
Basically my idea is to find the middle of the single linked list by using a quick (2 steps) and a slow (1 step) "pointer". After I found the middle, I push all values (the second half of the given array) into a stack (cache). The algorithm runs in O(n) and takes O(n) space. Hope this helps :-)
private static final Integer ZERO = 0;
public List<Integer> createNewList(final SingleLinkedNode<Integer> input) {
List<Integer> newList = null;
if (input != null) {
final Deque<Integer> cache = createNewListCache(input);
newList = new ArrayList<Integer>(cache.size() * 2);
SingleLinkedNode<Integer> current = input;
while (current != null) {
Integer tmp = cache.size() > 0 ? cache.pop() : ZERO;
newList.add(current.getElement() - tmp);
current = current.getNext();
}
}
return newList;
}
private Deque<Integer> createNewListCache(final SingleLinkedNode<Integer> input) {
Deque<Integer> cache = new ArrayDeque<Integer>();
SingleLinkedNode<Integer> slow = input;
SingleLinkedNode<Integer> quick =input;
while (quick != null) {
quick = quick.getNext();
if (quick != null) {
quick = quick.getNext();
slow = slow.getNext();
}
}
while (slow != null) {
cache.push(slow.getElement());
slow = slow.getNext();
}
return cache;
}
Space:O(n), Time :O(n)
rev = reverse_list(list);
while(true) {
if (list == rev || list.next == rev) {
list.data = list.data-rev.data;
break;
}
list.data = list.data-rev.data;
list = list.next;
rev = rev.next;
}
One thing to add is while reversing, we shouldn't just swap the values. But must swap the nodes to get the stopping condition right..
package datastructures.list;
class Node {
int data;
Node next;
public Node(int data2) {
data = data2;
next = null;
}
public Node() {
}
Node newnode(Node head, int data) {
if (head == null) {
return new Node(data);
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node(data);
return head;
}
}
void print(Node head) {
while (head != null && head.next != null) {
System.out.print(head.data + "->");
head = head.next;
}
if (head == null)
System.out.println("No nodes in the linked list");
else
System.out.println(head.data);
}
Node getMiddle(Node head){
Node tortoise = head,hare=head;
if(head == null)
return null;
while(hare !=null && hare.next !=null){
tortoise=tortoise.next;
hare=hare.next.next;
}
return tortoise;
}
void modifyLinkedList(Node head,Node lastNode){
while(lastNode!=null){
head.data=head.data-lastNode.data;
head=head.next;
lastNode=lastNode.next;
}
head.data=0;
}
Node reverseList(Node head){
Node current = head,next=null,temp=null;
while(current!=null){
next=current.next;
current.next=temp;
temp=current;
current=next;
}
return temp;
}
}
public class LinkedList {
public static void main(String[] args) {
Node linkedList = new Node();
Node head = null;
head = linkedList.newnode(head, 15);
head = linkedList.newnode(head, 24);
head = linkedList.newnode(head, 33);
head = linkedList.newnode(head, 22);
head = linkedList.newnode(head, 10);
linkedList.print(head);
Node mid = linkedList.getMiddle(head);
Node lastNode = linkedList.reverseList(mid.next);
linkedList.modifyLinkedList(head, lastNode);
mid.next= linkedList.reverseList(lastNode);
System.out.println();
linkedList.print(head);
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author nkbansal
*/
public class SubstractReverse {
static class ListNode{
ListNode next;
int data;
public ListNode(int data, ListNode next){
this.data = data;
this.next = next;
}
}
public static void main(String[] args) {
int[] input = {5, 4, 3, 2, 1};
ListNode next = null;
for(int i=input.length-1; i>=0;i--){
next = new ListNode(input[i], next);
}
printList(next);
System.out.println("Substract Reverse:");
substractReverse(next,next);
printList(next);
}
public static ListNode substractReverse(ListNode first, ListNode second){
ListNode toSubstract=null;
if (second.next != null){
if(second.next.next != null){
toSubstract = substractReverse(first.next, second.next.next);
}
else{
//E
toSubstract = first.next;
}
}
else{
//Even case
toSubstract = first;
}
first.data-=toSubstract.data;
return toSubstract.next;
}
public static void printList(ListNode node){
while(node!=null){
System.out.print(node.data+"->");
node = node.next;
}
System.out.println(""+null);
}
}
1. Use recursion with two pointer to get the center node.
2. Start backtracking from the center node by returning next pointer to each call.
3. Substract the value of next pointer from the current nodes values
Recursion works well here:
public void firstMinusLast(Node first, Node lastPlusOne) {
// are we done?
if (first == lastPlusOne)
return;
// find the last node (it's just before lastPlusOne)
Node last = first;
while (last.next != lastPlusOne)
last = last.next;
// now subtract the last value from the first value
first.val = first.val - last.val;
// recurse!
firstMinusLast(first.next, last);
}
The procedure can be divided into four steps:
(1)break up the list into the first half and the second half
(2)reverse the second half to use it as subtrahend
(3)minus each node of first half with each node of reverse of second half
(4)reverse the second half and connect it back to the first half's end
Complexity: time O(n), space O(1)
Following is C++ code:
- uuuouou May 12, 2014struct ListNode{ int val; ListNode* next; }; /* minus each of node in first half with the symmetric one in the second half */ ListNode* minusSymmetricNode(ListNode* head) { if(head == NULL) return NULL; if(head->next == NULL){ head->val = 0; return head; } //Step 1: use fast and slow pointer to break the list up at the (n + 1)/2 node ListNode* pFast = head->next, *pSlow = head; while(true){ if(pFast == NULL) break;//now pSlow points to the last node of the first half //and length of first half = length of second half + 1 if(pFast->next == NULL) break;//now pSlow points to the last node of the first half //and length of first half = length of second half pSlow = pSlow->next; pFast = pFast->next->next; } //if total length is odd, we set middle node' value to zero!!! if(pFast == NULL) pSlow->val = 0; //now slow->next is the head of second half ListNode* pSecondHalf = pSlow->next; pSlow->next = NULL; //Step 2: reverse second half and use it as subtrahend pSecondHalf = reverseList(pSecondHalf); //Step 3: minus each node of first half with each node of reverse of second half minus(head, pSecondHalf); //Step 4: reverse the second half and connect it to the first half's end pSlow->next = reverseList(pSecondHalf); return head; } ListNode* reverseList(ListNode* head)//reverse the list and return the new head { if(head == NULL || head->next == NULL) return head; ListNode *pre = NULL, *next = NULL; for(; head != NULL; head = next){ next = head->next; head->next = pre; pre = head; } return pre; } void minus(ListNode* minuend, ListNode* subtrahend)//minus each of minuend by each of subtrahend { while(minuend != NULL && subtrahend != NULL){ minuend->val -= subtrahend->val; minuend = minuend->next; subtrahend = subtrahend->next; } }