Swap list nodes
June 25, 2013
This is tricky. There are four possibilities:
1) If the list has less than k items (including the null list), return the list unchanged.
2) If the list has exactly 2k−1 items (the kth item is in the middle), return the list unchanged.
3) If the list has more than 2k−1 items, swap items k and n−k, where k is before n−k in the list.
4) If the list has less than 2k−1 items, swap items n−k and k, where n−k is before k in the list.
This can be done in a single pass using three pointers: Pointers a and b start from the beginning of the list and traverse k−1 nodes; if they reach the end of the list before traversing k−1 nodes, the original input list is returned unchanged. Then pointer b, which is still at the kth node, and pointer c, which is still at the beginning of the original input list, traverse nodes until b reaches the end of the list, at which point c points to the node k before the end of the list. If a and c point to the same node, return the original input list unchanged. Otherwise, swap the nodes pointed to by a and c and return the modified list. Here is our implementation:
(define (swap-kth-nodes xs k)
(let loop1 ((a xs) (b xs) (k (- k 1)))
(if (null? a) xs
(if (positive? k) (loop1 (cdr a) (cdr b) (- k 1))
(let loop2 ((b b) (c xs))
(if (pair? (cdr b)) (loop2 (cdr b) (cdr c))
(if (eq? a c) xs
(let ((t (car a)))
(set-car! a (car c)) (set-car! c t)
xs))))))))
The eq? performs pointer comparison; if a and c point to the same thing. Scheme provides that comparison because sometimes comparing pointers is quicker than comparing the objects to which the pointers point. Here are our tests:
> (swap-kth-nodes '() 3)
()
> (swap-kth-nodes '(1) 3)
(1)
> (swap-kth-nodes '(1 2) 3)
(1 2)
> (swap-kth-nodes '(1 2 3) 3)
(3 2 1)
> (swap-kth-nodes '(1 2 3 4) 3)
(1 3 2 4)
> (swap-kth-nodes '(1 2 3 4 5) 3)
(1 2 3 4 5)
> (swap-kth-nodes '(1 2 3 4 5 6) 3)
(1 2 4 3 5 6)
> (swap-kth-nodes '(1 2 3 4 5 6 7) 3)
(1 2 5 4 3 6 7)
> (swap-kth-nodes '(1 2 3 4 5 6 7 8) 3)
(1 2 6 4 5 3 7 8)
> (swap-kth-nodes '(1 2 3 4 5 6 7 8 9) 3)
(1 2 7 4 5 6 3 8 9)
You can run the program at http://programmingpraxis.codepad.org/jsSIqs0M.
Programming Praxis 
;; 1- test cases:
(defun test/swap-kth ()
(loop
:for (expected list k) :in ‘((() () 0)
(() () 1)
((x) (x) 0)
((x) (x) 1)
((b a) (a b) 0)
((b a) (a b) 1)
((a b) (a b) 2)
((c b a) (a b c) 0)
((a b c) (a b c) 1)
((c b a) (a b c) 2)
((a b c) (a b c) 3)
((d b c a) (a b c d) 0)
((a c b d) (a b c d) 1)
((a c b d) (a b c d) 2)
((d b c a) (a b c d) 3)
((a b c d) (a b c d) 4)
)
:for mutable = (copy-list list)
:for result = (swap-kth mutable k)
:do (assert (equal expected mutable)
() "(~S ‘~S ~S) -> ~S instead of expected ~S"
‘swap-kth list k result expected))
:success)
;; 2- a correct implementation.
(defun swap-kth (list k)
(check-type k (integer 0))
(when (< k (length list))
(rotatef (nth k list) (nth (- (length list) k 1) list)))
list)
(test/swap-kth)
;; –> :success
;; Notice that this correct implementation is O(n) time and O(1)
;; space, so it’s not bad. But it walks the list up to 4 times (could
;; be 3 times, factorizing out (length list).
;; We can write an optimized solution that walks the list only up to 2
;; times with O(1) space, or only once with O(n) space.
;; 3- an optimized solution, with still O(1) space:
;; we walk the list once to compute the length, and then down
;; (max k (- length k 1)).
(defun swap-kth (list k)
(check-type k (integer 0))
(let ((len (length list))) ; 1st walk.
(when (< k len)
(let* ((l (- len k 1))
(i (min k l))
(j (max k l))
(a (nthcdr i list))
(b (nthcdr (- j i) a)))
(rotatef (car a) (car b))))
list))
(test/swap-kth)
;; –> :success
;; 4- an optimized solution using Θ(n) space, but amortized only Θ(n)
;; time, walking the list only once. It builds a vector parallel
;; to the list.
(defun swap-kth (list k)
(check-type k (integer 0))
(let ((v (make-array 1 :adjustable t :fill-pointer 0)))
(loop
:for cell :on list
:do (vector-push-extend cell v (array-dimension v 0)))
(let ((len (length v))) ; O(1)
(when (< k len)
(let* ((l (- len k 1)))
(rotatef (car (aref v k)) (car (aref v l))))))
list))
(test/swap-kth)
;; –> :success
Here’s a Rackety version (although this one should work in most any Scheme): Swap list nodes on jverkamp.com
; Given a list, swap the kth from head and tail (define (swap-kth ls k) ; Get pointers to the kth head and the kth tail (define-values (_ kth-head kth-tail) (let loop ([i 1] [ls ls]) (cond [(null? ls) (values 1 #f #f)] [else (define-values (j kth-head kth-tail) (loop (+ i 1) (cdr ls))) (values (+ j 1) (if (= i k) ls kth-head) (if (= j k) ls kth-tail))]))) ; Recur again, swapping the pointers (let loop ([ls ls]) (cond [(null? ls) '()] [(eq? ls kth-head) (cons (car kth-tail) (loop (cdr ls)))] [(eq? ls kth-tail) (cons (car kth-head) (loop (cdr ls)))] [else (cons (car ls) (loop (cdr ls)))])))Check out the link above for test cases and a bit of discussion. Two9 things that were particularly neat was the use of
eq?for quick pointer comparison and the relative simplicity of the code so far as dealing with special cases goes. Granted, it doesn’t bail early ifkth-headiseq?tokth-tail, but that would be easy enough to add.Here’s my version. Not particularly elegant.
(define (swap a b) (define (swap_ k xs) (define len (length xs)) (define (swap__ k xs) (let ((k1 (+ k 1))) (append (take k xs) (list (list-ref xs (- len k1))) (take (- len (* k1 2)) (drop k1 xs)) (list (list-ref xs k)) (drop (- len k) xs)))) (define k1 (+ k 1)) (cond ((or (< k 0) (< len 1) (>= k len) (= k1 (/ (+ len 1) 2))) xs) (else (swap__ (if (> k1 (/ len 2)) (- len k1) k) xs)))) (cond ((and (integer? a) (list? b)) (swap_ a b)) ((and (integer? b) (list? a)) (swap_ b a)) (else #f)))The real work is done in swap__ appending the results of a take, a drop-take, a drop, and two list-refs. The swap_ function just checks for edge cases. The body of the outer function checks the types of the parameters and allows the user to pass them in either order.
def change_list(mylist,place):
temp = mylist[place-1]
mylist[place-1] = mylist[len(mylist)-place]
mylist[len(mylist)-place] = temp
return mylist
mylist = [1,2,3,4,5,6,7,8,9]
print (change_list(mylist,6))