Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- x = a+c
- y = b+c
- x = a+c
- y = b+c
- z = a+b
- a = (+x-y+z)/2
- b = (-x+y+z)/2
- c = (+x+y-z)/2
- lenA = count(listA) //iterates list A
- lenB = count(listB) //iterates list B
- ptrA = listA
- ptrB = listB
- //now we adjust either ptrA or ptrB so that they are equally far from the end
- while(lenA > lenB):
- ptrA = ptrA->next
- lenA--
- while(lenB > lenA):
- prtB = ptrB->next
- lenB--
- while(ptrA != NULL):
- if (ptrA == ptrB):
- return ptrA //found merge point
- ptrA = ptrA->next
- ptrB = ptrB->next
- A-->B-->C
- |
- V
- 1-->2-->3-->4-->5
- A B C
- 1-->2-->3 4 5
- //pseudocode
- //for the first list
- p1=list1;
- unsigned int addr[];//to store addresses
- i=0;
- while(p1!=null){
- addr[i]=&p1;
- p1=p1->next;
- }
- int len=sizeof(addr)/sizeof(int);//calculates length of array addr
- //for the second list
- p2=list2;
- while(p2!=null){
- if(search(addr[],len,&p2)==1)//match found
- {
- //this is the merging node
- return (p2);
- }
- p2=p2->next;
- }
- int search(addr,len,p2){
- i=0;
- while(i<len){
- if(addr[i]==p2)
- return 1;
- i++;
- }
- return 0;
- }
- -> A - Contains reference in Pointers? No, move on
- -> B - Contains reference in Pointers? No, move on
- -> C - Contains reference in Pointers? No, move on
- -> D - Contains reference in Pointers? Yes, merge point found, break.
- for each item in list a
- push pointer to item onto stack_a
- for each item in list b
- push pointer to item onto stack_b
- while (stack_a top == stack_b top) // where top is the item to be popped next
- pop stack_a
- pop stack_b
- // values at the top of each stack are the items prior to the merged item
- Head A 0x7fffb2f3c4b0
- 0x214f010
- 0x214f030
- 0x214f050
- 0x214f070
- 0x214f090
- 0x214f0f0
- 0x214f110
- 0x214f130
- 0x214f150
- 0x214f170
- Head B 0x7fffb2f3c4a0
- 0x214f0b0
- 0x214f0d0
- 0x214f0f0
- 0x214f110
- 0x214f130
- 0x214f150
- 0x214f170
- next_node = node->next;
- node = (struct node*)((unsigned long)node | 0x1UL);
- real_node = (struct node*)((unsigned long)node) & ~0x1UL);
- real_node = real_node->next;
- node = real_node;
Add Comment
Please, Sign In to add comment