Given a linked list, swap the kth element from the start with the kth element from the end.
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
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.