coding c linked list algorithm problems

Published on September 15th, 2013 | by Luke Queenan

3

Copying Linked Lists with Random Pointers

The other day while burning a few minutes before a meeting, a colleague showed me the following problem:

Copy a single linked list where each node has three pointers; data, next, and a random pointer to any other node in the list (forwards or backwards).

Linked list with random pointers to other nodes in the list.

As the diagram above illustrates, the quirk that makes this problem interesting is the random pointer. Since it can point many nodes ahead or behind, assigning this value in the copied list must wait until the whole list has first been copied.

Since the meeting started before we could discuss our solutions, I felt compelled to try and solve the problem later that day. My initial solution was as follows:

  • Create a copy of the original list, ignoring the random pointers
  • During this required first pass for generating the copy list, have a hash map where the memory address for each node in the original list is used as a key, with the corresponding copy node’s memory address as the value.
  • Run through both lists using the random pointer value in the original list to obtain the corresponding pointer for the copy list, then inserting that value into the copy list’s random pointer.

While this solution works perfectly fine, doing some research revealed that there was a more elegant solution that wouldn’t require the use of C++ (God intended us to program in C on a good day, C++ on a bad day) or creating my own hash map in C. In fact, this solution wouldn’t require any other data structures besides the copy list. The overall process is as follows:

  • Copy the first node and insert it between the first node and the second. Then copy the second node and insert it between the second and third nodes. Continue this pattern along the length of the list. Ignore the random pointers for now.
  • Now copy the random pointers as follows, using the knowledge that “next” is pointing towards the copy of the original. This is where the real magic happens.
1
srcCurrent->next->random = srcCurrent->random->next;
  • All that remains is to separate the lists.
1
2
srcCurrent->next = srcCurrent->next->next;
cpyCurrent->next = cpyCurrent->next->next;

After the second step (just before the lists are to be separated), the linked list appears as follows in memory (red is the copied list).

Original linked list, but with the copy nodes inserted and random pointers assigned.

You can easily trace the random pointer assignment calls by hand and get a good visual of the solution.

There are a few things to note about each of these approaches. The first doesn’t require altering the original list and should be O(n) for both time complexity and auxiliary space. The second is O(n) for time complexity but O(1) for auxiliary space, and the original list must be modified.

After discussing this second solution with my colleague, he asked, “How could you design the algorithm to be able to cleanly recover (ie: not modify the first list) if there was an out of memory exception?”. This requires checking the return of malloc for the NULL pointer and then joining the original list up to the node we reached, while calling free on the copy nodes.

Here is my implementation of the copy and the rollback functions in C.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
void rollback(node *src, node *end)
{
    node *srcCurrent = src;
    node *temp = NULL;
 
    while (srcCurrent != end) {
        temp = srcCurrent->next;
        srcCurrent->next = srcCurrent->next->next;
        srcCurrent = srcCurrent->next;
        free(temp);
    }
}
 
node *copy(node *src)
{
    node *srcCurrent = src;
    node *cpyCurrent = NULL;
    node *newHead = NULL;
 
    // Insert a copy of the current node after itself
    while (srcCurrent) {
        // Make space for, and assign, copy data
        cpyCurrent = malloc(sizeof(node));
        if (cpyCurrent == NULL) {
            rollback(src, srcCurrent);
            return NULL;
        }
        cpyCurrent->data = srcCurrent->data;
        cpyCurrent->next = srcCurrent->next;
 
        // Insert the copied node (got next in previous line)
        srcCurrent->next = cpyCurrent;
 
        srcCurrent = srcCurrent->next->next;
    }
 
    srcCurrent = src;
 
    // Copy the random pointers
    while (srcCurrent) {
        srcCurrent->next->random = srcCurrent->random->next;
        srcCurrent = srcCurrent->next->next;
    }
 
    srcCurrent = src;
    cpyCurrent = srcCurrent->next;
    newHead = cpyCurrent;
 
    // Seperate the lists
    while (cpyCurrent->next) {
        // Original list
        srcCurrent->next = srcCurrent->next->next;
        srcCurrent = srcCurrent->next;
 
        // Copied list
        cpyCurrent->next = cpyCurrent->next->next;
        cpyCurrent = cpyCurrent->next;
    }
    srcCurrent->next = NULL;
 
    return newHead;
}

You can find the full source code for the sample application that creates the linked list, assigns the “random” pointers, and then copies and prints the result here.

Tags: , ,


About the Author

is a software developer specializing in network security, client-server models, application piracy protection, and keeping fit in the gym.



3 Responses to Copying Linked Lists with Random Pointers

  1. Nandha says:

    Superb idea. Very easy to follow. Thanks.

  2. tanglei says:

    nice~
    It is easy to understand.

  3. Prathyusha says:

    wow!! u help me!…your explanation is good! Thank u

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Current ye@r *

Back to Top ↑