Find the middle item in a Linked List
int find_middle(node *head)
{
node *p1, *p2;
p1 = p2 = head;
while (p1 != NULL && p1->next != NULL) {
p1 = p1->next->next; // p1 goes 2 steps; p2 goes 1 step
p2 = p2->next;// when p1 to the end, p2 points to middle
}
return p2;
}
Determine if there is a loop in a Linked List
bool find_loop(node *head)
{
node *p1, *p2;
p1 = p2 = head;
while (p1 != NULL && p1->next != NULL) {
p1 = p1->next->next;// p1 goes 2 steps; p2 goes 1 step
p2 = p2->next;
if (p1 == p2) // If there is loop, we must get p1 == p2
return true; // sooner or later
}
return false; // If goes out of the while, no loop.
}
Find merge point of two Linked Lists (if there is one)
Node* Find_merge_point(Node *h1, Node *h2)
{
Node *p1, *p2;
int n = Length1(h1) - Length1(h2);
if (n >= 0) { // make p1 to be longer one
p1 = h1;
p2 = h2;
}
else {
n *= -1;
p1 = h2;
p2 = h1;
}
while (n--)// n is the length diff. between p1 and p2
p1 = p1->next; // make p1 and p2 "aligned"
while (p1 != p2 && p1 != NULL && p2 != NULL) {
p1 = p1->next; // start to check merge point
p2 = p2->next;
}
if (p1 == NULL || p2 == NULL) {
printf("can't find merge point!\n");
return NULL;
}
else
return p1;
}
沒有留言:
張貼留言