Coding Kata – February 1st 2010 – Flippin’ Lists
2.01.2010 | Kata
Goal: Flip tuples in a doubly linked list.
Example: Given A <-> B <-> C <-> D, have an algorithm produce B <-> A <-> D <-> C.
Constraints: All manipulations must be made to the original linked list, and minimize use of external data structures as much as possible.
Hmmm of the day: The ideal solution is fairly brief and elegant, so don’t try to over-think it unless you need to!
2.01.2010
Killin’ time before an interview. This seems like a productive way to do that.
while( notDone ){
zeroth = node.prev
first = node
second = node.next
third = second.next
if(zeroth != null){
zeroth.next=second
}
second.next=first
second.prev = zeroth
first.next=third
first.prev=second
if(third != null){
third.prev = first
}
//If no more after this pair, or only one more, end
if( third == null || third.next == null ){
notDone = false
}
else{
//skip up to the next pair
node = node.next.next
}
}
2.02.2010
Sweet, there it is!
6.12.2010
For those that want some elegance (and are okay with value-rewriting instead of link-rewriting which AFAIK is fine in most functional languages), try this one out: https://gist.github.com/1b84be2b4c91d95b52c1
P.S. Kevin, your solution fails where the linked list has length less than three.
P.P.S. Chris, hope things are going well. Interesting problem. The spec should probably say “flip 2-tuples” or “flip pairs”, though, as a “tuple” is just any ordered list.