הפרוצדורה:

void delete_node(node *to_del,node *a1,node *b1)
{
node *p1=a1;
node *tp1=p1;
node *p2=b1;
node *tp2=p2;
int c1,c2,tc1,tc2;
c1=c2=tc1=tc2=0;
while(to_del != p1 && to_del != p2 && to_del != tp1 && to_del != tp2  && p1!=p2 && tp1!=tp2)
{
	while(c1<c2)
	{
		++c1;
		p1=p1->next;
	}
	++c2;
	p2=p2->next;
	while(tc2<tc1)
	{
		++tc2;
		tp2=tp2->next;
	}
	++tc1;
	tp1=tp1->next;
}  
if(p1 != p2 || tp1 != tp2 && to_del==p1 || to_del==tp1)
	remove(to_del,a1);
if(p1 != p2 || tp1 != tp2  && to_del==p2 || to_del==tp2)
	remove(to_del,a2)
}

עכשיו אני כמוכם מנסה לפתור בעצמי.
אם נגיד ל-2 המצביעים פשוט לרוץ על כל האפשרויות:
א. מצביע 1 מתקדם 0 מקומות, מצביע 2 מתקדם מקום 1 ולהפך.
ב. מצביע 1 מתקדם 1 מקומות, מצביע 2 מתקדם מקום 0 ולהפל.
ג. מצביע 1 מתקדם 1 מקומות, מצביע 2 מתקדם 1 מקום.
ד. מצביע 1 מתקדם 2 מקומות, מצביע 2 מתקדם 0 מקום ולהפך.
וכו' ...
אפשר לרשום בזוגות סדורים:

אנחנו נגלה את התא כאשר נרוץ פשוט על הזוג (m,k). סיבוכיות זמן הריצה הי איפוא m^2*k^2 שזה לא להיט (הריבועים שם כי כל פעם אנחנו חוזרים עם המצביעים להתחלה).
(אני ברגע זה חושב בעצמי, לכן ההסברים מתגבשים בזה הרגע )
נסמן d = max(m,k).
נניח אני מסתכל על איזשהו זוג (i,i) כש-i גדול מ-d. אני יודע שבודאות שניהם חצו את המכשול. אבל יש מישהו מהיר יותר, לכן בהכרח או ש-P1 יעקוף את P2 ואז בריצה השנייה (ש-P2 מתחיל) תהיה התנגשות. או להפך. אבל העיקר שהזוג הזה תופס.
כלומר יכולנו פשוט לרוץ על (i,i) כש-i הולך ועולה. בתפיסה הראשונה נדע גם מי מגיע מהר יותר לאיחוד (זה שתופס מן הסתם). נשים לב שהתפיסה הראשונה גם מבטאת בידיוק את max(m,k) שזה קצת מפתיע. למעשה היינו יכולים פשוט להגיד להם תרוצו כל פעם i צעדים כשפעם הראשון מתחיל, אחריו השני ואז להפך והתפיסה הראשונה בעצם תבטא את המקסימום, כי התפיסה הראשונה אומרת שהמצביע שמצביע על הרשימה הארוכה יותר סוף סוף נכנס לאיחוד ואז נתפס.
אז כמה זה עולה לנו עד פה? d^2
הבעייה שאנחנו לא יודעים מי המהיר יותר אז אנחנו כל פעם מחליפים את הריצה וזה מוסיף לנו ריבוע. אם למשל היינו רצים גם בקפיצות לוגירתמיות של 1,2,4,8 ועושים חיפוש בינארי על ה-d המיימלי אז זה היה עולה כבר dlog d, אבל זה עדיין לא ליניארי.
נו כל זה ב-6 בבוקר, אולי מספיק להיום?

הרעיון:
הזוג (i,i) יסמן לנו ריצה באופן הבא:
P1 רץ i צעדים ועוצר. P2 רץ i צעדים ועוצר.
& vice versa:
P2 רץ i צעדים ועוצר. P1 רץ i צעדים ועוצר.
כל פעם רצים מהתחלת הרשימה.

נשים לתובנה כי אם i<d אז אף אחד לא יפגוש באף אחד (כי יש מצביע שעדיין לא הגיע להצטלבות). אם i>=d אז נשים לב שהמצביע שמגיע מהר יותר להצטלבות יחתוך את המצביע האיטי בדרך. לכן אם P1 למשל המצביע האיטי ו-P2 המהיר, אז כאשר P1 ירוץ ויעצר, P2 יתפוס אותו.

ניסיון ראשון:
להתחיל מ-i=0, להגדיל אותו כל פעם וברגע שיהיה מפגש אז i = d וסיימנו. זה עולה לנו d^2.
ניסיון שני:
נרוץ בקפיצות של i = 1,2,4,8, ...
נשים כי כאשר:

מספר הצעדים שהמהיר עוקף את האיטי שווה בידיוק להפרש בין הרשימות. עכשיו שיש לנו את ההפרש בין 2 הרשימות, כלומר את |m-k| אז פשוט נקדם קודם כל את המצביע האיטי במספר הזה, נרוץ על שתי הרשימות במקביל וברגע שנעצור - הרי זה התא המיוחל.
כמה זה עולה לנו?
כל ריצה על (i,i) עולה לנו 2i ובגלל שרצנו בקפיצות זה עולה לנו:

O(1 + 2 + 4 + ... + d/2 + d + 2d) = O(4d)

ולבסוף עוד ריצה אחרונה