reverse a linked list in linear time, with constrained memory, no second container allowed.

Question

Andy · Accepted Answer

private void reverseList(Node *current, Node *prev) {
	if (current) {
			Node *temp = current->next;
			current->next = prev;
			return reverseList(temp, current);
	} else {
		return temp;
	}
}


TESTS:

===
T1:
Node *head = [1]->[2]->[3]->[4]->NULL
reverseList(head, NULL);

current = [1]->[2]->[3]->[4]->NULL
prev = NULL
temp = [2]->[3]->[4]->NULL
current = [1]->NULL
reverseList(temp, current)
---
current = [2]->[3]->[4]->NULL
prev = [1]->NULL
temp  = [3]->[4]->NULL
current = [2]->[1]->NULL
reverseList(temp, current)
---
current = [3]->[4]->NULL
prev = [2]->[1]->NULL
temp = [4]->NULL
current = [3]->[2]->[1]->NULL
reverseList(temp, current)
---
current = [4]->NULL
prev = [3]->[2]->[1]->NULL
temp = NULL
current = [4]->[3]->[2]->[1]
reverseList(temp, current)
---
current = NULL
temp = [4]->[3]->[2]->[1]->NULL
RETURN temp
===
T2:
Node *head = NULL;
reverseList(head, NULL);

RETURN NULL
===
T3:
Node *head = [1]->NULL;
reverseList(head, NULL);

current = [1]->NULL
prev = NULL
temp = NULL
current = [1]->NULL
reverseList(temp, current)
---
current = NULL
temp = [1]->NULL
RETURN temp
===

Mulatto401 · Answer

?// Will reverse the arr by swapping values

var arr = [1,2,3,4,5];
console.log(arr); 

for(var i=0; i < arr.length / 2; i++){
    var tmp = arr[i];
    arr[i] = arr[arr.length - i - 1];
    arr[arr.length -i - 1] = tmp;
}
    
console.log(arr);
?

Sigiloso · Answer

pointer manipulation on the elements of the linked list.

Anonymous · Answer

The general idea is to iterate through the list starting at the root, and assigning to the next item's 'next' pointer the current item. That is, if a -> b -> c -> NULL, we first set a -> NULL, then b -> a, then c -> b, yielding NULL next',
// I replace that with 'b'.

while (current_item->next != NULL) {           // 1: b != NULL , 2: c != NULL , 3: NULL == NULL
    next_item = current_item->next;              // 1: next_item=b , 2: next_item=c
    current_item->next = previous_item;       // 1: a->next=NULL , 2: b->next=a
    previous_item = current_item;                 // 1: previous_item=a , 2: previous_item=b
    current_item = next_item;                        // 1: current_item=b, 2: current_item=c
}

// Note that this is necessary to set the last item in the original list to be the first item
// in the new list. Also, note that if the list has just 1 item, previous_item will evaluate
// to NULL, and the behavior is as expected.
current_item->next = previous_item;           // c->next = b

OkCupid

Pergunta de entrevista da empresa OkCupid

Respostas da entrevista

Empresas seguidas

Buscas de vagas