3
\$\begingroup\$

Given a linked list and two positions m and n. The task is to rotate the sub-list from position m to n, to the right by k places. (link to GeeksforGeeks)

Examples

Input: list 1->2->3->4->5->6, m = 2, n = 5, k = 2

Output: 1->4->5->2->3->6

Explanation: Rotate the sub-list 2 3 4 5 towards right 2 times then the modified list is: 1 4 5 2 3 6

Input: list = 20->45->32->34->22->28, m = 3, n = 6, k = 3

Output: 20->45->34->22->28->32

Explanation: Rotate the sub-list 32 34 22 28 towards right 3 times then the modified list is: 20 45 34 22 28 32

// Rotate the sub-list of a linked list from position M to N to the right by K places

#include <iostream>
using namespace std;

//  structure of the node in the linked list
struct Node {
    int data;
    Node* next;
};

// inserting at the beggining
void push( Node **head, int data ) {
    Node *newNode = new Node();
    newNode->data = data;

    if((*head) == NULL) {
        (*head) = newNode;
        return;
     }

    Node *temp = (*head);
    while(temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
    newNode->next = NULL;
  }

// display
void display(Node *head) {
    cout << "The list : \t";
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}

// Rotate the linked list by k
void rotate(Node *head, int m, int n, int k) {
    Node *temp1 = head ;
    Node *temp3 = NULL, *ref = NULL, *last = NULL;

    for (int i = 0; i < m - 1 ; i++)
        temp1 = temp1->next;
    ref = temp1->next;
    temp3 = ref ;

    for (int i = 0; i < n - m; i++)
        temp3 = temp3->next;
    last = temp3->next;
    temp3->next = ref ;

    k = k%(n - m + 1);

    for(int i = 0; i < k; i++) {
        temp3 = ref;
        ref = ref->next;
    }
    temp3->next = last;

    // if the starting point is not 1st element
    if (m == 0)
        head = ref;
    else
        temp1->next = ref;

    display(head);
}

// Driver function
int main() {
    Node *head = NULL;

    push(&head, 1);
    push(&head, 2);
    push(&head, 3);
    push(&head, 4);
    push(&head, 5);
    push(&head, 6);
    push(&head, 7);

    display(head);

    cout << "\n\n";
    int m, n, k;
    cout << "m, n, k = \t";
    cin >> m >> n >> k ;

    rotate(head, m - 1, n - 1, k);
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Please do not update the code in your question to incorporate feedback from answers; doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Edward Dec 21 '18 at 12:38
3
\$\begingroup\$

I see a number of things that may help you improve your program.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.

Make sure the comments don't mislead

The code currently includes this comment and function:

// inserting at the beggining
void push( Node **head, int data ) {

However, that comment is false (and spelled incorrectly). In fact, the data is appended to the end of the linked list. For that reason, I'd suggest changing the name to append.

Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful.

Return something useful from functions

It is not very useful to have every function return void. Instead, I'd suggest that push (now renamed to append per previous suggestion) could return a pointer to the head of the list. Here's one way to write that:

// append data to end of linked list
Node* append(Node *head, int data) {
    auto newNode = new Node{data, nullptr};
    if (head == nullptr) {
        return newNode;
    }
    auto temp{head};
    while (temp->next) {
         temp = temp->next; 
    }
    temp->next = newNode;
    return head;
}

Don't leak memory

This code calls new but never delete. This means that the routines are leaking memory. It would be much better to get into the habit of using delete for each call to new and then assuring that you don't leak memory.

Use objects

The Node object is a decent start, but I'd recommend and actual linked list object to better take care of memory management and node initialization.

Sanitize user input

If the user enters a negative number or a number that's larger than the array, or numbers that are not in the right order, bad things happen in the current program. In general, it's better to be very wary of user input and test for and handle any bad input.

Fix the bug

If the subsequence includes the first node, the output is incorrect. That's a bug.

Rethink the problem

There are two essential parts to the algorithm. First, we identify the subsequence and then we do the rotation. With some thought, you can figure out either 0 or 3 next links will need to be changed. We can immediately understand that if \$n - m + 1 = k \mod (n-m+1)\$ then no links need to change and we're done. Otherwise 3 links need to change. Let's number each of the nodes, starting from 1. So the first node is \$N[1]\$, and the second is \$N[2]\$, etc.

  • Now the first node that needs to be altered is \$N[m-1]\$. It needs to point to \$N[m + k]\$.
  • Next \$N[n]\$ (the last node of the subset) points to \$N[m]\$ (the first of the subset).
  • Then \$N[m + k - 1]\$ must point to \$N[n+1]\$

With that in mind, it should be apparent that only a single pass through the data structure is needed with only two temporary pointers. I'll leave it to you to write the code for that.

\$\endgroup\$
  • \$\begingroup\$ thank you very much for the detailed response, i was able to learn many new things. \$\endgroup\$ – Error_loading Dec 20 '18 at 9:18
  • \$\begingroup\$ I’m glad you found it helpful! I enjoyed thinking about the problem. \$\endgroup\$ – Edward Dec 20 '18 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.