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
using System ; public class Node { public int data ; public Node next ; public Node ( int d ) { data = d ; next = null ; } } public class LinkedList { Node head ; void push ( int new_data ) { Node new_node = new Node ( new_data ) ; new_node . next = head ; head = new_node ; } void printList ( ) { Node node = head ; while ( node != null ) { Console . Write ( node . data + " ▁ " ) ; node = node . next ; } Console . WriteLine ( " " ) ; } int countNodes ( ) { int count = 0 ; Node s = head ; while ( s != null ) { count ++ ; s = s . next ; } return count ; } void swapKth ( int k ) { int n = countNodes ( ) ; if ( n < k ) return ; if ( 2 * k - 1 == n ) return ; Node x = head ; Node x_prev = null ; for ( int i = 1 ; i < k ; i ++ ) { x_prev = x ; x = x . next ; } Node y = head ; Node y_prev = null ; for ( int 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 ; Node temp = x . next ; x . next = y . next ; y . next = temp ; if ( k == 1 ) head = y ; if ( k == n ) head = x ; } public static void Main ( String [ ] args ) { LinkedList llist = new LinkedList ( ) ; for ( int i = 8 ; i >= 1 ; i -- ) llist . push ( i ) ; Console . Write ( " Original ▁ linked ▁ list : ▁ " ) ; llist . printList ( ) ; Console . WriteLine ( " " ) ; for ( int i = 1 ; i < 9 ; i ++ ) { llist . swapKth ( i ) ; Console . WriteLine ( " Modified ▁ List ▁ for ▁ k ▁ = ▁ " + i ) ; llist . printList ( ) ; Console . WriteLine ( " " ) ; } } }