How can the runner technique be used to arrange this linked list?

  • Thread starter Thread starter ainster31
  • Start date Start date
  • Tags Tags
    List
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
3 replies · 4K views
ainster31
Messages
158
Reaction score
1

Homework Statement



POpQu.png


Homework Equations





The Attempt at a Solution



I don't understand how when p1 hits the end of the linked list, p2 will be at the midpoint.

This is how I am imagining it if n=3. Each step below represents an iteration.

1. a1 (p1, p2)->a2->a3->b1->b2->b3

2. a1->a2 (p2)->a3 (p1)->b1->b2->b3

3. a1->a2->a3 (p2)->b1->b2 (p1)->b3

4. Index out of bounds error because p2 now points to a node after b3.
 
Physics news on Phys.org

Discussion

It says you don't know the list length but you do know that its length is even.

Hence you can't have n=3 in your thought experiment.

So if n=10 then:

i=0 p1=0 p2=2
i=1 p1=1 p2=4
i=2 p1=2 p2=6
i=3 p1=3 p2=8
i=4 p1=4 p2=0 // p2 is reset to the beginning of the list and p1 is at the midpoint
 
  • Like
Likes   Reactions: 1 person
Oh, so I guess they wanted n to be even. Even if n is odd, the linked list length is even since the length of the linkedlist is 2n.
 
ainster31 said:
Oh, so I guess they wanted n to be even. Even if n is odd, the linked list length is even since the length of the linkedlist is 2n.

Only the linked list length is even, if n is half the list length then n can be even or odd.