Question

C++ language or Python.

Linked Lists

You are given a linked list that contains N integers. You are to perform the following reverse operation on the list:

• Select all the subparts of the list that contain only even integers. For example, if the list is {1,2,8,9,12,16}, then the selected subparts will be {2,8}, {12,16}.

• Reverse the selected subpart such as {8,2} and {16,12}.

• The list should now be {1,8,2,9,16,12}.

Your node definition should consist of 2 elements: the integer value and a pointer to a node.

Sample Input

9 2 18 24 3 5 7 9 6 12

Sample Output:

24 18 2 3 5 7 9 12 6

Answer 1

C++

// Iterative C++ program to reverse

// a linked list

#include <iostream>

using namespace std;

/* Link list node */

struct Node {

    int data;

    struct Node* next;

    Node(int data)

    {

        this->data = data;

        next = NULL;

    }

};

struct LinkedList {

    Node* head;

    LinkedList()

    {

        head = NULL;

    }

    /* Function to reverse the linked list */

    void reverse()

    {

        // Initialize current, previous and

        // next pointers

        Node* current = head;

        Node *prev = NULL, *next = NULL;

        while (current != NULL) {

            // Store next

            next = current->next;

            // Reverse current node's pointer

            current->next = prev;

            // Move pointers one position ahead.

            prev = current;

            current = next;

        }

        head = prev;

    }

    /* Function to print linked list */

    void print()

    {

        struct Node* temp = head;

        while (temp != NULL) {

            cout << temp->data << " ";

            temp = temp->next;

        }

    }

    void push(int data)

    {

        Node* temp = new Node(data);

        temp->next = head;

        head = temp;

    }

};

/* Driver program to test above function*/

int main()

{

    /* Start with the empty list */

    LinkedList ll;

    ll.push(20);

    ll.push(4);

    ll.push(15);

    ll.push(85);

    cout << "Given linked list\n";

    ll.print();

    ll.reverse();

    cout << "\nReversed Linked list \n";

    ll.print();

    return 0;

}

Python

# Python program to reverse a linked list # Time Complexity : O(n) # Space Complexity : O(1) # Node class class Node:     # Constructor to initialize the node object     def __init__(self, data):         self.data = data         self.next = None class LinkedList:     # Function to initialize head     def __init__(self):         self.head = None     # Function to reverse the linked list     def reverse(self):         prev = None         current = self.head         while(current is not None):             next = current.next             current.next = prev             prev = current             current = next         self.head = prev               # Function to insert a new node at the beginning     def push(self, new_data):         new_node = Node(new_data)         new_node.next = self.head         self.head = new_node     # Utility function to print the linked LinkedList     def printList(self):         temp = self.head         while(temp):             print temp.data,             temp = temp.next # Driver program to test above functions llist = LinkedList() llist.push(20) llist.push(4) llist.push(15) llist.push(85) print "Given Linked List" llist.printList() llist.reverse() print "\nReversed Linked List" llist.printList()