-2

I'm trying to code a function which will be used to rotate linked list in this way: 1 -> 2 -> 3 -> 4, if the user choose the first node to be moved 3 nodes forward it's going to be: 2->3->1->4->END(Switch between two nodes until it gets to third node, it looks to me like bubble sort). Another example: If the user choose the second node to be first it's going to look like this: 2->1->3->4->END.

Saga
  • 67
  • 1
  • 8
  • 2
    That's not *sorting*, that's just simple swapping places of nodes. And you usually do that for a list by reassigning the pointers of the nodes you're moving. – Some programmer dude Jun 14 '17 at 08:53
  • @Someprogrammerdude To second your comment, linked lists can be implemented in such a way that they have artificial additional nodes for its head and tail in order to remove edge cases in the swapping if one of the involved nodes is at the start or at the end. – Codor Jun 14 '17 at 08:56
  • I don't think it is related to any sorting algorithm anyway. What you think should be output for the link list: `3->1->7->10->5->12->8->END`, if I choose to move element `7` by 2. – cse Jun 14 '17 at 08:58
  • Your example moves the node by 2 not by 3. – stark Jun 14 '17 at 09:59
  • @cse Do you mean to move the seventh element(8) or to move the third element(7)? – Saga Jun 14 '17 at 10:19
  • @stark Sorry, I meant to move the node to the third node. – Saga Jun 14 '17 at 10:20
  • 1
    @Saga No I mean to move 3rd element(7) by 2 steps. – cse Jun 14 '17 at 10:24
  • @cse The function takes the position, so do you mean to move the third element to the 5th element? – Saga Jun 14 '17 at 10:28
  • 1
    @Saga Yes!!! So, If we move 3rd element(7) by 2 steps then list will be `3->1->10->5->7->12->8->END`. This is normal shifting. My point was that: _This is related to any sorting algorithm_. Because If we perform any `sorting` algorithm(for example `bubble sort`) on this list then output will be different(In this case, after 1st iteration output will be `1->3->7->5->10->8->12->END`). – cse Jun 14 '17 at 10:43
  • 3->1->10->5->7->12->8 Yep, you right. But I'm still having problems with writing this function.. @cse – Saga Jun 14 '17 at 11:11
  • Swap the value of the node (K-1) times. – BLUEPIXY Jun 14 '17 at 12:47

2 Answers2

0

Probably like the following process. (Untested pseudocode)

void rotateLeftOne(Node *np, int rotateLength){
    if(np == NULL || np->next == NULL)
        return;
    assert(rotateLength <= listLength(np));
    for(int i = 1; i < rotateLength && np->next; ++i, np = np->next){
        swap(&np->value, &np->next->value);
    }
}
BLUEPIXY
  • 39,699
  • 7
  • 33
  • 70
0

Following is the required code snip-it which will perform the required action. You can see the complete working here. Function void shiftNode(Node** rootNode, int nodeIndex, int shifts) in the code to shift a node to required places:

typedef struct N
{
    int val;
    struct N* next;
}Node;

/** Index starts from 0*/
void shiftNode(Node** rootNode, int nodeIndex, int shifts)
{
    int i=1;
    Node *pNode, *temp, *root = *rootNode;
    if((shifts <= 0) || (nodeIndex < 0))
    {
        return;
    }

    if(nodeIndex != 0)
    {
        for(i=1; i<nodeIndex; i++)
        {
            root = root->next;
        }
        pNode = root->next;
        root->next = pNode->next;
    }
    else
    {
        *rootNode = root->next;
        pNode = root;
        root->next = pNode->next;
    }

    for(i=0; i<shifts; i++)
    {
        root = root->next;
    }
    temp=root->next;
    root->next = pNode;
    pNode->next=temp;
}
cse
  • 4,066
  • 2
  • 20
  • 37