Rotate a Linked List

Problem:

Given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer.

Approach:

To rotate the linked list, we need to change next of kth node to NULL, next of last node to previous head node, and finally change head to (k+1)th node. So we need to get hold of three nodes: kth node, (k+1)th node and last node.

Solution:

void rotateList(Node *&head, int k)

{

     if (k == 0)

       return;

    Node* curr = head;

    int count = 1;

    while (count < k && curr != NULL)

    {

        curr = curr->next;

        count++;

    }

    if (curr == NULL)

        return;

    Node *kthNode = curr;

    while (curr->next != NULL)

        curr = curr->next;

    curr->next = head;

    head = kthNode->next;

    kthNode->next = NULL;

}

Pairwise swap nodes of a given linked list.

void pairWiseSwap(Node *&head)
{
    if (head == NULL || head->next == NULL)
        return;

    Node *prev = head;
    Node *curr = head->next;

    head = curr;

    while (1)
    {
        Node *next = curr->next;
        curr->next = prev;

        if (next == NULL || next->next == NULL)
        {
            prev->next = next;
            break;
        }

        prev->next = next->next;
        prev = next;
        curr = prev->next;
    }
}

Average salary of n people in the room.

Question:

How can n people know the average of their salaries without disclosing their own salaries to each other?

Solution:

Let's say salaries of n people (P1, P2, P3.....Pn) are S1, S2, S3.....Sn respectively. To know the average of the salary i.e. (S1 + S2 + S3 + ..... + Sn) / n, they will follow the following steps -

1. P1 adds a random amount, say R1 to his own salary and gives that to P2 (P2 won't be able to know P1's salary as he has added a random amount known to him only). In this case, P2 will receive the figure (S1 + R1) from P1.
2. P2 does the same and gives the final amount to P3 (without showing that to anyone). Now P3 will get the figure (S1 + R1 + S2 + R2).
3. Rest of the persons (P3, P4, P5.....Pn) do the same. Pn will give the final amount to P1. Now P1 will have (S1 + R1 + S2 + R2 + S3 + R3 + ...... + Sn + Rn).
4. Now P1 subtracts his random amount (R1) and gives the final figure to P2 (without showing that to anyone). P2 will now receive the figure (S1 + R1 + S2 + R2 + S3 + R3 + .... Sn  + Rn) - R1 = (S1 + S2 + R2 + S3 + R3 + ...... + Sn + Rn).
5. P2 subtracts his random amount (R2) and gives the final figure to P3 (without showing it to anyone). P3 will receive the amount (S1 + S2 + S3 + R3 + ..... Sn + Rn).
6. In the same way every person remaining except (Pn) will subtract their random amount and give it to the next one. Now Pn will have (S1 + S2 + S3 + ..... Sn + Rn).
7. Now Pn subtracts his random amount (Rn) and then the figure becomes (S1 + S2 + S3 + .... + Sn). Pn will divide this amount by n and get the average i.e. (S1 + S2 + S3 + ..... + Sn) / n and show to every one in the room.

(Puzzle was asked in the Yahoo interview)