Answer to Question #276255 in C++ for zain

Question

1.   Programming Problem I ( Singly Linked List)

Given a singly linked list of size N, the task is to left-shift the linked list by k nodes where k is the given positive integer smaller than or equal to the length of linked list.

For example:

Input:           N=5

2-> 4-> 7-> 8-> 9

K=3

Output:                               8-> 9-> 2-> 4-> 7

Answer 1

#include <iostream>
using namespace std;

class List {
    struct Node {
        Node(int v) {
            x = v;
            next = nullptr;
        }
        int x;
        Node* next;
    };
    Node* head;


public:
    List() : head(nullptr) {}
    ~List();
    void add(int x);
    void print();
    void shift(int k);
};

void List::add(int x) {
    Node* node = new Node(x);
    node->next = head;
    head = node;
}


List::~List() {
    while(head) {
        Node* tmp = head->next;
        delete head;
        head = tmp;
    }
}

void List::print() {
    if (!head) {
        cout << "<NULL>" << endl;
        return;
    }
    cout << head->x;
    Node* cur = head->next;
    while (cur) {
        cout << "->" << cur->x;
        cur = cur->next;
    }
    cout << endl;
}


void List::shift(int k) {
    if (k <= 0) {
        cerr << "shift: non positive K" << endl;
        return;
    }
    Node* node = head;
    for (int i=0; i<k-1; ++i) {
        if (!node->next) {
            cerr << "shift: K is too big" << endl;
            return;
        }
        node = node->next;
    }
    
    Node* cur = head;
    while (cur->next) {
        cur = cur->next;
    }
    cur->next = head;
    head = node->next;
    node->next = nullptr;
}

int main()
{
    const int n=5, k=3;
    int arr[n] = {9, 8, 7, 4, 2};
    List list;


    for (int i=0; i<n; ++i) {
        list.add(arr[i]);
    }


    cout << "Source list:" << endl;
    list.print();
    
    cout << "List shifted by " << k << ":" << endl;
    list.shift(k);
    list.print();


}