I'm working on a reverse-linked list problem where you reverse a sub-list within the Linked-list structure. The sublist is defined with left and right which is the portion you must reverse. When working with smaller sized Linked Lists (size 2) it works fine but when working with 5 elements or so, it begins to fail. This is because (as seen in the example) I do not quite understand how to maintain the original head and connect to my now reversed sub-list. I have tried head->next = prev; but this did not work and resulted in nullptr memory access error.
Quite new to this data structure and would appreciate any insight into how I might go about solving the issue.
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(0, head);
ListNode* prev = nullptr;
ListNode* current = head;
int counter = 1;
while (current != nullptr)
{
if (counter == left)
{
ListNode* lastKnownParent = current;
ListNode* n = nullptr;
while (counter <= right)
{
n = current->next;
current->next = prev;
prev = current;
current = n;
counter ;
}
lastKnownParent->next = current;
}
else {
counter ;
current = current->next;
}
}
dummy->next->next = current;
dummy->next = prev;
return dummy->next;
}
Success with smaller sized:
input: [3,5] left = 1, right = 2: Output: [5,3]
Fail with larger size:
input: [1,2,3,4,5] left = 2, right = 4: Output: [2,4,3,2,5]
CodePudding user response：
There are a few issues:
The lines at the bottom of your function are not good. They hard-code that some change needs to happen at the first two nodes of the list, but this makes no sense when for example the reversal has to take place between nodes 4 and 6. So those two lines should be removed:
dummy->next->next = current; dummy->next = prev;The node that precedes
lastKnownParentwill have to get itsnextpointer updated, but the problem is that there is no direct reference anymore to that node. The statements I quoted above were probably meant to reach that node, but it has to be done relative to theleftposition.
To illustrate what goes wrong, look at this visualisation when we have a list of 8 nodes and the two given positions are left=4 and right=6:
When reaching left and entering the loop, we get this state:
lastKnownParent
dummy head current n
↓ ↓ ↓ ↓
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 0 ├──►│ 1 ├──►│ 2 ├──►│ 3 ├──►│ 4 ├──►│ 5 ├──►│ 6 ├──►│ 7 ├──►│ 8 │
└───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘
prev == nulltptr
When reaching right, the loop makes one more iteration and then the loop exits, resulting in this state:
dummy head lastKnownParent prev current n
↓ ↓ ↓ ↓ ↓ ↓
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 0 ├──►│ 1 ├──►│ 2 ├──►│ 3 ├──►│ 4 │◄──┤ 5 │◄──┤ 6 │ │ 7 ├──►│ 8 │
└───┘ └───┘ └───┘ └───┘ └─┬─┘ └───┘ └───┘ └───┘ └───┘
▼
nullptr
Your code then correctly sets the next pointer of the node with value 4 (lastKnownParent):
dummy head lastKnownParent prev current n
↓ ↓ ↓ ↓ ↓ ↓
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 0 ├──►│ 1 ├──►│ 2 ├──►│ 3 ├──►│ 4 │◄──┤ 5 │◄──┤ 6 │ │ 7 ├──►│ 8 │
└───┘ └───┘ └───┘ └───┘ └─┬─┘ └───┘ └───┘ └─▲─┘ └───┘
└───────────────────────┘
But there is one thing missing. The link from node 3 to node 6 still needs to be made. This is something you seem to have tried at the very end of your function, but you cannot assume that it is always dummy->next->next that needs to change. This depends on left, or in other words, it depends on lastKnownParent. The problem is that lastKnownParent points to the successor of the node that needs this update. So, make lastKnownParent to point to the predecessor instead, at the time it is initialised. Then you can make both updates (first updating node 4, then node 3). Then it would look like this:
dummy head lastKnownParent prev current n
↓ ↓ ↓┌──────────────────────┐↓ ↓ ↓
┌───┐ ┌───┐ ┌───┐ ┌─┴─┐ ┌───┐ ┌───┐ ┌▼──┐ ┌───┐ ┌───┐
│ 0 ├──►│ 1 ├──►│ 2 ├──►│ 3 │ │ 4 │◄──┤ 5 │◄──┤ 6 │ │ 7 ├──►│ 8 │
└───┘ └───┘ └───┘ └───┘ └─┬─┘ └───┘ └───┘ └─▲─┘ └───┘
└───────────────────────┘
To make it possible to set lastKnownParent one node earlier, you could for instance have prev follow behind current even in the first iterations -- when left is not yet encountered.
Here is the corrected code, with comments where something changed:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(0, head);
ListNode* prev = dummy; // prev follows behind current
ListNode* current = head;
int counter = 1;
while (current != nullptr)
{
if (counter == left)
{
ListNode* lastKnownParent = prev; // one node earlier
ListNode* n = nullptr;
while (counter <= right)
{
n = current->next;
current->next = prev;
prev = current;
current = n;
counter ;
}
// lastKnownParent is now one node earlier than in your code
lastKnownParent->next->next = current;
lastKnownParent->next = prev; // now the mutation is complete...
break; // ... so we don't need to iterate the remaining nodes.
}
else {
counter ;
prev = current; // prev follows behind current
current = current->next;
}
}
// Removed two statements here
return dummy->next;
}
Further improvements
This code assumes that the given positions are valid. You may want to improve on this and determine what should happen when one or both are out of range, or right is less than left.
You may also want to think of more elegant ways to solve this challenge. For instance, you could create functions that can:
- inverse a complete list
- split a list at a certain position into two smaller lists.
- concatenate smaller lists into one
This may lead to code that is more readable.