Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
public static Node updateLinkedList(Node head) {
if (head == null) {
return null;
}
Node slow = head;
Node fast = head;
Stack<Node> stack = new Stack<Node>();
while (fast != null){
stack.push(slow);
fast = fast.next;
if (fast != null) {
slow = slow.next;
fast = fast.next;
}
}
while(!stack.isEmpty()) {
Node temp = stack.pop();
slow.value = temp.value + slow.value;
slow = slow.next;
}
return head;
}
public static Node updateLinkedList(Node head) {
if (head == null) {
return null;
}
Node slow = head;
Node fast = head;
Stack<Node> stack = new Stack<Node>();
while (fast != null){
stack.push(slow);
fast = fast.next;
if (fast != null) {
slow = slow.next;
fast = fast.next;
}
}
while(!stack.isEmpty()) {
Node temp = stack.pop();
slow.value = temp.value + slow.value;
slow = slow.next;
}
return head;
}
public ListNode secondHalf(ListNode root){
if(root == null) return null;
ListNode fast = root;
ListNode slow = root;
Stack<Integer> stack = new Stack<Integer>();
while(fast!=null && fast.next!= null){
stack.push(slow.val);
slow = slow.next;
fast = fast.next.next;
}
if(fast != null)
stack.push(slow.val);
while(slow!=null && !stack.isEmpty()){
slow.val += stack.pop();
slow= slow.next;
}
return root;
}
public ListNode secondHalf(ListNode root){
if(root == null) return null;
ListNode fast = root;
ListNode slow = root;
Stack<Integer> stack = new Stack<Integer>();
while(fast!=null && fast.next!= null){
stack.push(slow.val);
slow = slow.next;
fast = fast.next.next;
}
if(fast != null)
stack.push(slow.val);
while(slow!=null && !stack.isEmpty()){
slow.val += stack.pop();
slow= slow.next;
}
return root;
}
void Update(Node *head)
{
int size = 0;
for (Node *n = head; n != NULL; n = n->next_) {
++size;
}
int half = size / 2;
stack<int> st;
int i = 0;
for (Node *n = head; n != NULL; n = n->next_, ++i) {
if (size % 2 == 1 ? i <= half : i < half) {
st.push(n->val_);
}
if (i >= half) {
n->val_ += st.top();
st.pop();
}
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static class LList {
LList(int data) {
this.data = data;
}
LList(int data, LList down, LList next) {
this.data = data;
this.down = down;
this.next = next;
}
LList() {
this.data = Integer.MAX_VALUE;
}
@Override
public String toString() {
return " " + this.data + " ";
}
int data;
LList next;
LList prev;
LList rand;
LList down;
}
public static void main(String args[]) throws Exception {
LList head = new LList(1);
head.next = new LList(2);
head.next.next = new LList(3);
//head.next.next.next = new LList(4);
updateLinkedList(head);
}
public static LList updateLinkedList(LList head) {
LList temp = head;
LList prev = null;
LList slow = head;
LList fast = head;
Stack<LList> stack = new Stack<LList>();
int len = 0;
while (temp != null) {
temp = temp.next;
len++;
}
while (slow != null && fast != null) {
prev = slow;
stack.push(slow);
slow = slow.next;
fast = fast.next;
if (fast != null)
fast = fast.next;
}
if (len % 2 == 0)
prev = prev.next;
while (!stack.isEmpty()) {
prev.data = stack.pop().data + prev.data;
prev = prev.next;
}
return head;
}
}
- shweta.agarwal21 August 30, 2017