A Solution of A Written Question in An Examination (1)

Posted on

Question

Assume an Slist L, with a data structure of each node as following:

1
2
3
4
5
struct node
{
    int num;
    node* next;
};

Complete the function as following, where for each ordinal sublist with n nodes, the function is able to reserve its order, and return the new head of the list. For the last sublist, do not reserve its order if the number of nodes is less than n.

1
2
3
4
5
6
node* f(node* head, int n)
{
    /****************************/
    /* Add your code here. */
    /****************************/
}

Feature head is the first node of the slist, n is the given number. This function will return the first node of the list.

Solution

Assume that we have a list of the length 3, thus we can complete the code as following.

1
2
3
4
5
6
7
8
node* f(node* head)
{
    node* former(head->next), temp(head->next->next), letter(head->next->next->next);
    former->next = head;
    temp->next = former;
    letter->next = temp;
    return head;
}

For the list L with the length n(n >= 3), we can saberate it as n lists, each of which has one node that needs transforming.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
node* f(node* head, int n)
{
    node* former(head->next);
    node* temp(head->next->next);
    node* letter(head->next->next->next);
    former->next = head;
    for(int i = 1; i < n; i++)
    {
        temp->next = former;
        former = temp;
        temp = letter;
        letter = letter->next;
    }
    temp->next = former;
    return temp;
}

With the combination of the algorithm shown and the considerition of that it is used in a sublist with the length n, we can complete the solution of this problem as following consequently.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
node* f(node* head, int n)
{
    node* former(head->next);
    node* temp(head->next->next);
    node* letter(head->next->next->next);
    node* header(head); // The node before the first one
    node* header_temp(head);
    node* tail(head);   // The node after the last one
    do
    {   
        for(int i = 1; i <= n || !tail; i++)
        {
            tail = tail->next;
        }
        if(!tail) break;
        else
        {
            tail = tail->next;
            former->next = tail;
            header_temp = former;   // Save the node as the one before the first node of the next group of nodes
            for(int i = 1; i < n; i++)
            {
                temp->next = former;
                former = temp;
                temp = letter;
                letter = letter->next;
            }
            temp->next = former;
            header->next = temp;
            header = header_temp;   // Refresh header
            continue;
        }
    }while(1);  // while
    return head;
}   // f