How to "slice" Linked lists

Question

so I am given the head of a linked list and an index i, how do I slice a linked list in such a way that looks like this

>>> LL = A - B - C - D - E - F
>>> slice(LL, 3)
>>> LL
E - F - D - A - B - C

I know how to find the ith node, but then i get stuck on how to link the last node to the ith node, and then the ith node to the head of the list, which should give me the above transformation

thanks in advance!

Answer 1

Is the new position of 'D' possibly a typo?
(like it's supposed to be D-E-F-A-B-C, which is more straightforward?)

Otherwise it looks like you select element 3 (D, assuming a 0-index), then flip the other two segments around it...which is fine (just different), so that's why I'm checking.

Answer 2

Well...assuming full iteration / not doubly-linked (no backlinks):

You're basically iterating two linked lists and swapping their heads and tails (through D).

(ABC) D (EF)
[LIST_X] D [LIST_Y]

xHead[...]xTail D yHead[...]yTail

You're breaking these links:
yTail -> xHead
xTail -> D
D -> yHead

To create:
(EF) D (ABC)
yHead[...]yTail D xHead[...]xTail

So......
temp = yTail.link (xHead)
yTail.link = referenceToD
D.link = temp (saved xHead)
xTail.link = referenceTo_yHead

If iterating from 0...end, you'd keep updating your reference to "xTail" until you found your split-element (you wouldn't update xTail then), save a reference to D, save D's link as yHead, then iterate to the end, save the last element's link to temp, then finish the update steps (you're at yTail, and you kept references to everything else that breaks as you went along).

I really hope that's not super confusing.

Answer 3

it should be just as I wrote it, elements start at index 0

Answer 4

i hope it helps clarify

Answer 5

i still don't get it. do i have to create 2 empty lists to append the first half and then the second half is that what you mean ?