Swap Kth node from beginning with Kth node from end in a Linked List | A Linked List node ; * Utility function to insert a node at the beginning ; Utility function for displaying linked list ; * Utility function for calculating length of linked list ; * Function for swapping kth nodes from both ends of linked list ; Count nodes in linked list ; Check if k is valid ; If x ( kth node from start ) and y ( kth node from end ) are same ; Find the kth node from beginning of linked list . We also find previous of kth node because we need to update next pointer of the previous . ; Similarly , find the kth node from end and its previous . kth node from end is ( n - k + 1 ) th node from beginning ; If x_prev exists , then new next of it will be y . Consider the case when y -> next is x , in this case , x_prev and y are same . So the statement " x _ prev - > next ▁ = ▁ y " creates a self loop . This self loop will be broken when we change y -> next . ; Same thing applies to y_prev ; Swap next pointers of x and y . These statements also break self loop if x -> next is y or y -> next is x ; Change head pointers when k is 1 or n ; Driver code to test above
class Node { constructor ( val ) { this . data = val ; this . next = null ; } } var head ; function push ( new_data ) { new_node = new Node ( new_data ) ; new_node . next = head ; head = new_node ; } function printList ( ) { node = head ; while ( node != null ) { document . write ( node . data + " " ) ; node = node . next ; } document . write ( " " ) ; } function countNodes ( ) { var count = 0 ; s = head ; while ( s != null ) { count ++ ; s = s . next ; } return count ; } function swapKth ( k ) { var n = countNodes ( ) ; if ( n < k ) return ; if ( 2 * k - 1 == n ) return ; x = head ; x_prev = null ; for ( i = 1 ; i < k ; i ++ ) { x_prev = x ; x = x . next ; } y = head ; y_prev = null ; for ( i = 1 ; i < n - k + 1 ; i ++ ) { y_prev = y ; y = y . next ; } if ( x_prev != null ) x_prev . next = y ; if ( y_prev != null ) y_prev . next = x ; temp = x . next ; x . next = y . next ; y . next = temp ; if ( k == 1 ) head = y ; if ( k == n ) head = x ; } for ( let i = 8 ; i >= 1 ; i -- ) push ( i ) ; document . write ( " " ) ; printList ( ) ; document . write ( " " ) ; for ( let i = 1 ; i < 9 ; i ++ ) { swapKth ( i ) ; document . write ( " " + i + " " ) ; printList ( ) ; document . write ( " " ) ; }