Reverse Operations

Feb 7, 202010 mins read

Straight to the Point !

Are you landed to this page and rushing for the immediate solution in javascript. here you go !!

  1. Step 1: goes_here
  2. Step 2: goes_here
  3. Step 3: goes_here
1function reverse(head) {
2// write your code here
3 let dummy = new Node(0);
4 dummy.next = head;
5 // Declare previous and current value.
6 let previous = dummy;
7 let current = head;
8 // While Loop.
9 while (current) {
10 if (isEven(current.data)) {
11 previous.next = reverseNodes(current);
12 }
13 previous = current;
14 current = current.next;
15 }
16 return dummy.next;
17 // Reverse Nodes.
18 function reverseNodes(node) {
19 let current = node;
20 let previous = null;
21 while (current && isEven(current.data)) {
22 let next = current.next;
23 current.next = previous;
24 previous = current;
25 current = next;
26 }
27 node.next = current;
28 return previous;
29 }
30 // Check number isEven.
31 function isEven(num) {
32 return num % 2 === 0;
33 }
34}

On High level note, It worth to read in detail for a better understanding. This is one of the Facebook interview question and Leet code problem as well - 1460. leetCodetitle

Table of Contents

Problem Statement

You are given a singly-linked list that contains N integers. A subpart of the list is a contiguous set of even elements, bordered either by either end of the list or an odd element. For example, if the list is [1, 2, 8, 9, 12, 16], the subparts of the list are [2, 8] and [12, 16].

Then, for each subpart, the order of the elements is reversed. In the example, this would result in the new list, [1, 8, 2, 9, 16, 12].

The goal of this question is: given a resulting list, determine the original order of the elements.

Implementation detail:

You must use the following definition for elements in the linked list:

1class Node {
2 int data;
3 Node next;
4}

Constraints

  1. 1 <= N <= 1000, where N is the size of the list
  2. 1 <= Li <= 10^9, where Li is the ith element of the list

Expected

  1. Goes here

Test Cases

  1. Input: [1, 2, 8, 9, 12, 16] and Output: [1, 8, 2, 9, 16, 12]
  2. Input: [2, 18, 24, 3, 5, 7, 9, 6, 12] and Output: [24, 18, 2, 3, 5, 7, 9, 12, 6]

Foot Note

  1. Goes here

Solution Intro

Lets see the list of approaches and their complexities.


ApproachTime ComplexitySpace Complexity
1Brute ForceO(n+mO(m+n)
2$Approach 1$O(n)O(n)
3$Approach 2$O(n)O(n)
4Time OptimizedO(n)O(n)
5Memory OptimizedO(n)O(n)

Solutions

With no further due, lets take a example of code solutions.

Brute Force

Description

1Code goes here...

$Approach-1$

Description

1Code goes here...

$Approach-2$

Description

1Code goes here...

$Time-Optimized$

Description

1Code goes here...
### $Space-Optimized$Description
1Code goes here...