GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Algorithm/SortListUsingMergeAlgorithm.cpp at master · stepByStepToSky/Algorithm

Expand file tree

/

SortListUsingMergeAlgorithm.cpp

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
153 lines (136 loc) · 2.75 KB
/

SortListUsingMergeAlgorithm.cpp

Copy path

File metadata and controls

153 lines (136 loc) · 2.75 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
using namespace std;
struct ListNode
{
ListNode(int value) : val(value), next(nullptr) {}
int val;
ListNode * next;
};
ListNode * MergeTwoSortedList(ListNode * aHead, ListNode * bHead)
{
if (nullptr == aHead)
{
return bHead;
}
else if (nullptr == bHead)
{
return aHead;
}
ListNode * retHead = nullptr, * lastNode = nullptr;
if (aHead->val < bHead->val)
{
retHead = aHead;
lastNode = retHead;
aHead = aHead->next;
}
else
{
retHead = bHead;
lastNode = retHead;
bHead = bHead->next;
}
while (nullptr != aHead && nullptr != bHead)
{
if (aHead->val < bHead->val)
{
lastNode->next = aHead;
lastNode = aHead;
aHead = aHead->next;
}
else
{
lastNode->next = bHead;
lastNode = bHead;
bHead = bHead->next;
}
}
if (nullptr != aHead)
{
lastNode->next = aHead;
}
if (nullptr != bHead)
{
lastNode->next = bHead;
}
return retHead;
}
// list must contain two or more nodes
void SplitList(ListNode * head, ListNode ** firstHead, ListNode ** secondHead)
{
*firstHead = head;
ListNode * fast = head->next, * slow = head;
while (fast)
{
fast = fast->next;
if (nullptr != fast)
{
fast = fast->next;
slow = slow->next;
}
}
*secondHead = slow->next;
slow->next = nullptr; // split the whole list into two lists
}
ListNode * ListSortedByMerge(ListNode * head)
{
if (nullptr == head || nullptr == head->next)
{
return head;
}
ListNode * firstHead = nullptr, * secondHead = nullptr;
SplitList(head, &firstHead, &secondHead);
ListNode * firstSortedHead = ListSortedByMerge(firstHead);
ListNode * secondSortedHead = ListSortedByMerge(secondHead);
return MergeTwoSortedList(firstSortedHead, secondSortedHead);
}
void PushNode(ListNode ** head, ListNode ** lastNode, int value)
{
if (nullptr == *head)
{
*head = new ListNode(value);
*lastNode = *head;
return;
}
(*lastNode)->next = new ListNode(value);
*lastNode = (*lastNode)->next;
}
void PrintList(ListNode *head)
{
while (nullptr != head)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void DestoryList(ListNode *head)
{
while (nullptr != head)
{
ListNode * next = head->next;
delete head;
head = next;
}
}
int main()
{
ListNode * head = nullptr, * lastNode = nullptr;
PushNode(&head, &lastNode, 1);
PushNode(&head, &lastNode, 3);
PushNode(&head, &lastNode, 1);
PushNode(&head, &lastNode, 4);
PushNode(&head, &lastNode, 0);
PushNode(&head, &lastNode, 8);
PushNode(&head, &lastNode, 1);
PushNode(&head, &lastNode, 2);
PushNode(&head, &lastNode, 0);
PushNode(&head, &lastNode, 9);
PushNode(&head, &lastNode, 1);
PushNode(&head, &lastNode, 4);
cout << "before sort" << endl;
PrintList(head);
head = ListSortedByMerge(head);
cout << "after sort" << endl;
PrintList(head);
DestoryList(head);
}
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.