// Given a list, sort it using this method:
// reverse(lst, i, j), which reverses lst from i to j`.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Node
{
int data;
public:
Node(int newData)
{
data = newData;
}
int GetData() { return data; };
Node* next;
};
Node* getTail(Node* listPtr)
{
Node* lst = listPtr;
while (lst)
lst = lst->next;
return lst;
}
Node* swapNodes(Node* start, Node* end, Node* head)
{
Node* temp = head;
Node* curr = start;
Node* startPrev = nullptr;
Node* endPrev = nullptr;
// get start's prev
while (temp && temp->next != start) { temp = temp->next; };
startPrev = temp;
temp = start;
// get end's prev
while (temp && temp->next != end) { temp = temp->next; };
endPrev = temp;
temp = start->next; // store start->next
// check if the two nodes are neighbors
if (start->next == end)
{
start->next = end->next; // order matters here
end->next = start; // dont want to set end->next to end (infinite loop)
}
else
{
start->next = end->next; // order matters here
end->next = temp;
if (endPrev)
endPrev->next = start;
}
// make sure start is not head
if (startPrev)
{
startPrev->next = end;
return nullptr;
}
else // reset the head node
return end;
}
Node* SortList(Node* head, int h, int k)
{
Node* newHead = head;
Node* current = head;
Node* start = nullptr;
Node* end = nullptr;
// walk the start node to h
for (int i = 1; i < h; ++i)
{
if(current->next)
current = current->next;
}
start = current;
for (int i = h; i < k; ++i)
{
if (current->next)
current = current->next;
}
end = current;
current = start;
Node* hold1 = nullptr;
Node* hold2 = nullptr;
Node* temp = nullptr;
Node* headReset = nullptr;
int its = ((k - h) / 2 + 1);
for (int i = 0; i < its; ++i)
{
if (start == end)
break;
else
{
// store the next two nodes to return to
hold1 = start->next;
Node* temp = start;
while (temp && temp->next != end) { temp = temp->next; };
hold2 = temp;
// swap outer nodes
headReset = swapNodes(start, end, newHead);
}
start = hold1;
end = hold2;
if (headReset)
{
newHead = headReset;
headReset = nullptr;
}
}
return newHead;
}
int main()
{
Node* list = new Node(1);
list->next = new Node(2);
list->next->next = new Node(3);
list->next->next->next = new Node(4);
list->next->next->next->next = new Node(5);
list->next->next->next->next->next = new Node(6);
Node* newList = SortList(list, 3, 6);
while (newList)
{
cout << newList->GetData() << ", ";
newList = newList->next;
}
cout << endl;
return 0;
}
Kommentare