CodeStepByStep

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.

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

          +---+---+    +---+---+    +---+---+    +---+---+
list2 --> | 5 |   |--> | 6 |   |--> | 7 |   |--> | 8 | / |
          +---+---+    +---+---+    +---+---+    +---+---+

          +---+---+    +---+---+                                 +---+---+
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
};