Swap list nodes

June 25, 2013

We have today another from our never-ending list of interview questions:

Given a linked list, swap the kth node from the head of the list with the kth node from the end of the list.

Your task is to write a function to perform the indicated task; be sure to test it thoroughly. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

4 Responses to “Swap list nodes”

  1. ;; 1- test cases:

    (defun test/swap-kth ()
    :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))

    ;; 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)))

    ;; –> :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))))

    ;; –> :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)))
    :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))))))

    ;; –> :success

  2. JP said

    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])
            [(null? ls)
             (values 1 #f #f)]
             (define-values (j kth-head kth-tail)
               (loop (+ i 1) (cdr ls)))
              (+ j 1)
              (if (= i k) ls kth-head)
              (if (= j k) ls kth-tail))])))
      ; Recur again, swapping the pointers
      (let loop ([ls ls])
          [(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 if kth-head is eq? to kth-tail, but that would be easy enough to add.

  3. fisherro said

    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)))
              (take k xs)
              (list (list-ref xs (- len k1)))
              (take (- len (* k1 2))
                    (drop k1 xs))
              (list (list-ref xs k))
              (drop (- len k)
        (define k1 (+ k 1))
        (cond ((or (< k 0)
                   (< len 1)
                   (>= k len)
                   (= k1 (/ (+ len 1)
              (else (swap__ (if (> k1 (/ len 2))
                              (- len k1)
      (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.

  4. pytonist said

    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))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: