Ordering a linked list efficiently
I got this question in an interview which is like this:
IF I have a linked list like this,
1-> 2-> 3-> 4-> 5-> 6
I need to convert it to
1-> 6-> 2-> 5-> 3-> 4
And if so,
1-> 2-> 3-> 4-> 5-> 6-> 7
I need to convert it to
1-> 7-> 2-> 6-> 3-> 5-> 4
And most importantly, I need to change the original linked list and I cannot create a new linked list. I was thinking about recursion for this. But I couldn't work it out. Moreover, their limitation was due to the fact that the function for this can only have the title of the linked list.
source to share
This can be done in linear time O(n)
and usually during interviews, which (unfortunately) are considered more than the reliability of the solution.
You can do this by dividing the original list into two (as) equally sized (if possible) list, then flipping the second and concatenating both of them element by element (first element from the first list, second element from the second list, etc.) ... You don't need a lot of free space as you can simply use existing pointers.
For example:
1->2->3->4->5->6
1->2->3 and 4->5->6 // after split, 3 points to null, 4 is head of second list
1->2->3 and 4<-5<-6 // after reorder
1->6->2->3 and 4<-5 // first phase of merge
1->6->2->5->3 and 4 // second phase of merge
1->6->2->5->3->4 // last phase of merge
You can find the split point with running pointer
. You are traversing a list with one pointer going one node at a time, and one going two nodes at a time. When the faster pointer hits the end (null), the slower pointer will be before splitting, the node before splitting should then point to null instead of the next node (in our case, instead of 4), and the next node (4) becomes the head of the second list.
Reversing the second list and merging is a simple pointer replacement.
Just watch out for null pointers :-)
source to share
This can be done using a recursive algorithm. You need to spiral down the list (first-last-first-last). So my idea is to separate the first and last element of the list, concatenate them, and recursively do the same with the rest of the elements.
Here's a rough outline of the algorithm:
modifyList(head):
if head.next == null or head.next.next == null: # when the list contains 1 or 2 elements, keep it unchanged
return head
nextHead = head.next # head of the list after removing head and last item
last = head.next
beforeLast = head
while last.next != null: # find the last item, and the item before it
beforeLast = last
last = last.next
head.next = last # append last item after first
beforeLast.next = null # remove the last item from list
last.next = modifyList(nextHead) # recursively modify the 'middle' elements and append to the previous last item
return head
source to share
Here's a recursive way to do it.
Create a function nreverse
that changes the linked list in place. Common Lisp has this feature.
In the main list of a list, if the list is longer than one item, the nreverse
list is after the first item. In the diagram:
(setcdr listx (nreverse (cdr listx)))
Repair the following list box. Here's everything in Common Lisp:
? (defun munge (listx)
(let ((balx (cdr listx)))
(if (null balx)
listx
(progn (rplacd listx (nreverse balx))
(munge (cdr listx))
listx))))
MUNGE
? (munge '(1 2 3))
(1 3 2)
? (munge '(1 2 3 4 5 6))
(1 6 2 5 3 4)
? (munge '(1 2 3 4 5 6 7))
(1 7 2 6 3 5 4)
?
source to share