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 @ args : data : value of node ; Print linked list ; count number of node in 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
class Node : NEW_LINE INDENT def __init__ ( self , data , next = None ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = next NEW_LINE DEDENT DEDENT class LinkedList : NEW_LINE INDENT def __init__ ( self , * args , ** kwargs ) : NEW_LINE INDENT self . head = Node ( None ) NEW_LINE DEDENT def push ( self , data ) : NEW_LINE INDENT node = Node ( data ) NEW_LINE node . next = self . head NEW_LINE self . head = node NEW_LINE DEDENT def printList ( self ) : NEW_LINE INDENT node = self . head NEW_LINE while node . next is not None : NEW_LINE INDENT print ( node . data , end = " ▁ " ) NEW_LINE node = node . next NEW_LINE DEDENT DEDENT def countNodes ( self ) : NEW_LINE INDENT count = 0 NEW_LINE node = self . head NEW_LINE while node . next is not None : NEW_LINE INDENT count += 1 NEW_LINE node = node . next NEW_LINE DEDENT return count NEW_LINE DEDENT def swapKth ( self , k ) : NEW_LINE INDENT n = self . countNodes ( ) NEW_LINE if n < k : NEW_LINE INDENT return NEW_LINE DEDENT if ( 2 * k - 1 ) == n : NEW_LINE INDENT return NEW_LINE DEDENT x = self . head NEW_LINE x_prev = Node ( None ) NEW_LINE for i in range ( k - 1 ) : NEW_LINE INDENT x_prev = x NEW_LINE x = x . next NEW_LINE DEDENT y = self . head NEW_LINE y_prev = Node ( None ) NEW_LINE for i in range ( n - k ) : NEW_LINE INDENT y_prev = y NEW_LINE y = y . next NEW_LINE DEDENT if x_prev is not None : NEW_LINE INDENT x_prev . next = y NEW_LINE DEDENT if y_prev is not None : NEW_LINE INDENT y_prev . next = x NEW_LINE DEDENT temp = x . next NEW_LINE x . next = y . next NEW_LINE y . next = temp NEW_LINE if k == 1 : NEW_LINE INDENT self . head = y NEW_LINE DEDENT if k == n : NEW_LINE INDENT self . head = x NEW_LINE DEDENT DEDENT DEDENT llist = LinkedList ( ) NEW_LINE for i in range ( 8 , 0 , - 1 ) : NEW_LINE INDENT llist . push ( i ) NEW_LINE DEDENT llist . printList ( ) NEW_LINE for i in range ( 1 , 9 ) : NEW_LINE INDENT llist . swapKth ( i ) NEW_LINE print ( " Modified ▁ List ▁ for ▁ k ▁ = ▁ " , i ) NEW_LINE llist . printList ( ) NEW_LINE print ( " " ) NEW_LINE DEDENT