Swap kth node from the start and end of the list.


  • 0
    H

    Given a linked list, swap the kth element from the start with the kth element from the end.

    For example,

    Given linked list:        
                                            1->3->5->7->9->11, and input k = 2
    
    After the swapping, the list becomes:     
                                            1->9->5->7->3->11

  • 0
    R

    Do a fast and slow pointers, with the initial distance of k. And at first you will have the kth node from the start, and when the fast pointer reach the end, you will get the kth node from the end, as it's where the slower pointer at.

    And since we need to swap the value, we need to store the node before and after the target pointer, thus we may adjust the initial distance between fast and slow pointer to (k-1), and then increase it to (k+1). I think it would be in time O(n-k) and memory O(1).

    Above is what I thought of on the scrach paper. Thanks.

        LinkedList slow = head, fast = head;
        for(int i=0;i<k-1;i++) fast = fast.next;
    ...
    //move slow and fast simultaneously
    
    LinkedList prev1 = fast
    LinkedList curr1 = fast.next;
    LInkedList next1 = fast.next.next;
    fast = next1;
    
    //conitnue moving
    ...
    //get prev2, curr2, next2,
    //swap.
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.