logo CodeStepByStep logo

12rest34-5678-61rest3-2475

Language/Type: C++ linked lists pointers
Author: Marty Stepp (on 11/04)

Write the code that will turn the "before" picture into the "after" picture by modifying links between the nodes shown.

If a given list node object does not appear in the "After" picture, you must delete it to free its memory.

In this problem there is a middle section labeled ...(rest of list 1)... This is to indicate a middle section of nodes within list1. In solving this problem you do not know exactly how many nodes are present in the middle section nor what their data values are. The final state of the lists should preserve the state of the middle section with respect to neighboring nodes. You can walk along list1 through its middle section to eventually reach the ending nodes storing 3 and 4.

You are writing code to turn the specific "before" picture below into the specific "after" picture, not a general piece of code that could work for any possible linked list of nodes.

Constraints: You are not allowed to change any existing node's data field value. Solve it by changing pointers. You may declare up to two ListNode* pointer variables (aside from list1 and list2) to point to any existing nodes. Do not allocate memory for any new ListNode objects (using the new keyword) in solving this problem.

Before
          +---+---+    +---+---+                                 +---+---+    +---+---+
list1 --> | 1 |   |--> | 2 |   |--> ... (rest of list 1) ... --> | 3 |   |--> | 4 | / |
          +---+---+    +---+---+                                 +---+---+    +---+---+

          +---+---+    +---+---+    +---+---+    +---+---+
list2 --> | 5 |   |--> | 6 |   |--> | 7 |   |--> | 8 | / |
          +---+---+    +---+---+    +---+---+    +---+---+
After
          +---+---+    +---+---+                                 +---+---+
list1 --> | 6 |   |--> | 1 |   |--> ... (rest of list 1) ... --> | 3 | / |
          +---+---+    +---+---+                                 +---+---+

          +---+---+    +---+---+    +---+---+    +---+---+
list2 --> | 2 |   |--> | 4 |   |--> | 7 |   |--> | 5 | / |
          +---+---+    +---+---+    +---+---+    +---+---+

Assume that you are using the following ListNode structure:

struct ListNode {
    int data;        // data stored in this node
    ListNode* next;  // a link to the next node in the list

    ListNode(int data = 0, ListNode* next = nullptr) { ... }   // constructor
};
Type your C++ solution code here:


This problem asks for bare code. Submit a fragment of C++ code as described. Do not write any main function or any function heading around your code; just write the lines of code that will produce the result described.

You must log in before you can solve this problem.


Log In

Need help?

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.