Given a singly linked list of size N, and an integer K. You need to swap the K^{th} node from the beginning and K^{th} node from the end of the linked list. Swap the nodes through the links. Do not change the content of the nodes.
 
Example 1:
Input:
N = 4,  K = 1
value[] = {1,2,3,4}
Output: 1
Explanation: Here K = 1, hence after
swapping the 1st node from the beginning
and end thenew list will be 4 2 3 1.
 
Example 2:
Input:
N = 5,  K = 7
value[] = {1,2,3,4,5}
Output: 1
Explanation: K > N. Swapping is invalid. 
Return the head node as it is.
 
Your Task: 
You do not need to read input or print anything. The task is to complete the function swapkthnode(), which has takes head of link list, N and K as input parameters and returns the new head.
The generated output will be 1 if you are able to complete your task. 
 
Expected Time Complexity: O(n)
Expected Auxillary space Complexity: O(1)
 
Constraints:
1 <= N <= 10^{3}
1 <= K <= 10^{3}

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(n)
Expected Auxiliary Space:  O(1)

Starter code:
#User function Template for python3

'''

Function Arguments :

		@param  : head (given head of linked list), k(value of k)

		@return : None, Just swap the nodes

		

# Node Class

class Node:

    def __init__(self, data):   # data -> value stored in node

        self.data = data

        self.next = None



'''

#Function to swap Kth node from beginning and end in a linked list.

def swapkthnode(head,num,k):

    # return head of new linked list

    #code here

Solutions:
def swapkthnode(head, num, k):
	if k > n:
		return head
	if k == n - k + 1:
		return head
	(beg, beg_prev) = (head, None)
	(end, end_prev) = (head, None)
	for i in range(1, k):
		beg_prev = beg
		beg = beg.next
	for i in range(1, n - k + 1):
		end_prev = end
		end = end.next
	if beg_prev is not None:
		beg_prev.next = end
	if end_prev is not None:
		end_prev.next = beg
	temp = beg.next
	beg.next = end.next
	end.next = temp
	if k == 1:
		head = end
	if k == n:
		head = beg
	return head


def swapkthnode(head, num, k):
	if k > n:
		return head
	if k == n - k + 1:
		return head
	(begin, begin_prev) = (head, None)
	(end, end_prev) = (head, None)
	for i in range(1, k):
		begin_prev = begin
		begin = begin.next
	for i in range(1, n - k + 1):
		end_prev = end
		end = end.next
	if begin_prev is not None:
		begin_prev.next = end
	if end_prev is not None:
		end_prev.next = begin
	temp = begin.next
	begin.next = end.next
	end.next = temp
	if k == 1:
		head = end
	if k == n:
		head = begin
	return head


def swapkthnode(head, num, k):
	if k > num:
		return
	(c1, prev1, prev2, c2) = (head, None, None, head)
	for i in range(k - 1):
		prev1 = c1
		c1 = c1.next
	for i in range(num - k):
		prev2 = c2
		c2 = c2.next
	if prev1:
		prev1.next = c2
	if prev2:
		prev2.next = c1
	(c1.next, c2.next) = (c2.next, c1.next)
	if k == 1:
		head = c2
	if k == num:
		head = c1
	return head


def swapkthnode(head, num, k):
	n = num
	if n < k:
		return
	if 2 * k - 1 == n:
		return
	x = head
	x_prev = Node(None)
	for i in range(k - 1):
		x_prev = x
		x = x.next
	y = head
	y_prev = Node(None)
	for i in range(n - k):
		y_prev = y
		y = y.next
	if x_prev is not None:
		x_prev.next = y
	if y_prev is not None:
		y_prev.next = x
	temp = x.next
	x.next = y.next
	y.next = temp
	if k == 1:
		head = y
	if k == n:
		head = x
	return head


def swapkthnode(head, num, k):
	if k > n:
		return head
	c = head
	p = None
	b = head
	d = None
	for i in range(1, k):
		p = c
		c = c.next
	for i in range(1, n - k + 1):
		d = b
		b = b.next
	if p != None:
		p.next = b
	if d != None:
		d.next = c
	(c.next, b.next) = (b.next, c.next)
	if k == 1:
		head = b
	if k == n:
		head = c
	return head


def removeNext(p):
	n = p.next
	p.next = n.next
	return n

def insert(prev, p):
	p.next = prev.next
	prev.next = p

def swapkthnode(head, num, k):
	if k > num:
		return head
	if k == num - k + 1:
		return head
	if k > num - k + 1:
		k = num - k + 1
	nh = Node(0)
	nh.next = head
	prev = nh
	for i in range(k - 1):
		prev = prev.next
	prev2 = prev
	for i in range(k - 1, num - k):
		prev2 = prev2.next
	if prev2 == prev.next:
		r2 = removeNext(prev2)
		insert(prev, r2)
	else:
		r2 = removeNext(prev2)
		r1 = removeNext(prev)
		insert(prev, r2)
		insert(prev2, r1)
	return nh.next


def swapkthnode(head, num, k):
	if k > num:
		return head
	t1 = head
	p1 = None
	c = 1
	while c < k:
		p1 = t1
		t1 = t1.next
		c = c + 1
	t2 = head
	p2 = None
	c = 1
	while c < num - k + 1:
		p2 = t2
		t2 = t2.next
		c = c + 1
	n1 = t1.next
	n2 = t2.next
	if t1.next == t2:
		if p1:
			p1.next = t2
		else:
			head = t2
		t1.next = n2
		t2.next = t1
	elif t2.next == t1:
		if p2:
			p2.next = t1
		else:
			head = t1
		t2.next = n1
		t1.next = t2
	else:
		if p1:
			p1.next = t2
		else:
			head = t2
		t1.next = n2
		t2.next = n1
		if p2:
			p2.next = t1
		else:
			head = t1
	return head
	return t


def swapkthnode(head, n, k):
	if k > n:
		return head
	if k == n - k + 1:
		return head
	(be, be_pr) = (head, None)
	(end, end_pr) = (head, None)
	for i in range(1, k):
		be_pr = be
		be = be.next
	for i in range(1, n - k + 1):
		end_pr = end
		end = end.next
	if be_pr is not None:
		be_pr.next = end
	if end_pr is not None:
		end_pr.next = be
	temp = be.next
	be.next = end.next
	end.next = temp
	if k == 1:
		head = end
	if k == n:
		head = be
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	if n % 2 == 1 and n // 2 == k - 1:
		return head
	if k > n // 2:
		k = n - k + 1
	end = n - k + 1
	i = 1
	temp = head
	prev1 = None
	first = second = prev2 = prev = None
	while temp:
		if i == k:
			prev1 = prev
			first = temp
		if i == end:
			prev2 = prev
			second = temp
		prev = temp
		temp = temp.next
		i += 1
	if n % 2 == 0 and n // 2 == k:
		prev1.next = second
		temp = second.next
		second.next = first
		first.next = temp
		return head
	elif k == 1:
		prev2.next = first
		temp = first.next
		first.next = None
		second.next = temp
		return second
	else:
		prev1.next = second
		temp = second.next
		second.next = first.next
		prev2.next = first
		first.next = temp
		return head


def swapkthnode(head, num, k):
	if head == None or head.next == None or k > num:
		return head
	curr = head
	prev_curr = None
	curr2 = head
	prev_curr2 = None
	for i in range(1, k):
		prev_curr = curr
		curr = curr.next
	for i in range(1, num - k + 1):
		prev_curr2 = curr2
		curr2 = curr2.next
	if prev_curr != None:
		prev_curr.next = curr2
	if prev_curr2 != None:
		prev_curr2.next = curr
	temp = curr.next
	curr.next = curr2.next
	curr2.next = temp
	if k == num:
		head = curr
	if k == 1:
		head = curr2
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	if head == None:
		return head
	(cur1, cur2) = (head, head)
	(prev_cur1, prev_cur2) = (None, None)
	for i in range(k - 1):
		prev_cur1 = cur1
		cur1 = cur1.next
	for i in range(num - k):
		prev_cur2 = cur2
		cur2 = cur2.next
	if prev_cur1 != None:
		prev_cur1.next = cur2
	if prev_cur2 != None:
		prev_cur2.next = cur1
	temp = cur1.next
	cur1.next = cur2.next
	cur2.next = temp
	if k == num:
		head = cur1
	if k == 1:
		head = cur2
	return head


def swapkthnode(head, n, k):
	if k > n:
		return head
	c = head
	pc = None
	cc = head
	pcc = None
	for i in range(1, k):
		pc = c
		c = c.next
	for i in range(1, n - k + 1):
		pcc = cc
		cc = cc.next
	if pc != None:
		pc.next = cc
	if pcc != None:
		pcc.next = c
	(c.next, cc.next) = (cc.next, c.next)
	if k == 1:
		head = cc
	if k == n:
		head = c
	return head


def swapkthnode(head, num, k):
	n = num
	if k > n or 2 * k - 1 == n:
		return head
	first_ptr = head
	second_ptr = head
	prev_first_ptr = None
	prev_second_ptr = None
	for i in range(1, k):
		prev_first_ptr = first_ptr
		first_ptr = first_ptr.next
	for i in range(1, n - k + 1):
		prev_second_ptr = second_ptr
		second_ptr = second_ptr.next
	if prev_first_ptr is not None:
		prev_first_ptr.next = second_ptr
	if prev_second_ptr is not None:
		prev_second_ptr.next = first_ptr
	temp = first_ptr.next
	first_ptr.next = second_ptr.next
	second_ptr.next = temp
	if k == 1:
		head = second_ptr
	if k == n:
		head = first_ptr
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	start = Node(0)
	start.next = head
	l = num - k + 1
	for i in range(1, num + 1):
		if i == k:
			first = head
		if i == l:
			second = head
		head = head.next
	first_next = first.next
	second_next = second.next
	head = start
	for i in range(1, num + 1):
		if i == k:
			head.next = second
			second.next = first_next
		if i == l:
			head.next = first
			first.next = second_next
		head = head.next
	return start.next


def swapkthnode(head, num, k):
	if k > num:
		return head
	if num % 2 != 0 and k == num // 2 + 1:
		return head
	k = min(k, num - k + 1)
	cur = num
	prevL = None
	nthNodeL = head
	while cur:
		if cur == k:
			break
		prevL = nthNodeL
		nthNodeL = nthNodeL.next
		cur -= 1
	cur = 1
	prev = None
	nthNodeF = head
	while cur < k:
		prev = nthNodeF
		nthNodeF = nthNodeF.next
		cur += 1
	if k == num // 2 and num % 2 == 0:
		temp = nthNodeL.next
		prev.next = nthNodeL
		nthNodeL.next = nthNodeF
		nthNodeF.next = temp
		return head
	if k == 1:
		temp = nthNodeF.next
		nthNodeL.next = temp
		prevL.next = nthNodeF
		nthNodeF.next = None
		return nthNodeL
	temp1 = nthNodeF.next
	temp2 = nthNodeL.next
	prev.next = nthNodeL
	nthNodeL.next = temp1
	prevL.next = nthNodeF
	nthNodeF.next = temp2
	return head
	return head


def get_kth_node_from_end(head, k):
	slow = head
	fast = head
	for i in range(k):
		if fast:
			fast = fast.next
		else:
			return -1
	while fast:
		slow = slow.next
		fast = fast.next
	return slow

def printList(head):
	cur = head
	while cur:
		print(cur.data, end=' ')
		cur = cur.next
	print()

def swapkthnode(head, n, k):
	if k > n:
		return head
	if k == n - k + 1:
		return head
	(beg, beg_prev) = (head, None)
	(end, end_prev) = (head, None)
	for i in range(1, k):
		beg_prev = beg
		beg = beg.next
	for i in range(1, n - k + 1):
		end_prev = end
		end = end.next
	if beg_prev is not None:
		beg_prev.next = end
	if end_prev is not None:
		end_prev.next = beg
	temp = beg.next
	beg.next = end.next
	end.next = temp
	if k == 1:
		head = end
	if k == n:
		head = beg
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	if k == num - k + 1:
		return head
	start = head
	copy = k
	prev_start = None
	while k != 1:
		prev_start = start
		start = start.next
		k -= 1
	k = copy
	end = head
	end_index = num - k + 1
	prev_end = None
	while end_index != 1:
		prev_end = end
		end = end.next
		end_index -= 1
	if prev_start != None:
		prev_start.next = end
	if prev_end != None:
		prev_end.next = start
	store = start.next
	start.next = end.next
	end.next = store
	if k == 1:
		head = end
	if k == num:
		head = start
	return head


def swapkthnode(head, num, k):
	if k <= num:
		b = []
		tmp = head
		while tmp != None:
			b.append(tmp)
			tmp = tmp.next
		t = b[len(b) - k]
		m = b[k - 1]
		b[len(b) - k] = m
		b[k - 1] = t
		tmp = b[0]
		head = b[0]
		b.pop(0)
		for i in b:
			if i == b[-1]:
				tmp.next = i
				i.next = None
				return head
			tmp.next = i
			tmp = tmp.next
	return head


def swapkthnode(head, num, k):
	if num < k:
		return head
	if 2 * k - 1 == num:
		return head
	x = head
	x_prev = None
	for i in range(k - 1):
		x_prev = x
		x = x.next
	y = head
	y_prev = None
	for i in range(num - k):
		y_prev = y
		y = y.next
	if x_prev != None:
		x_prev.next = y
	if y_prev != None:
		y_prev.next = x
	temp = x.next
	x.next = y.next
	y.next = temp
	if k == 1:
		return y
	if k == num:
		return x
	return head


def swapkthnode(head, n, k):
	p = head
	q = head
	r = head
	s = head
	if k > n:
		return head
	if k == 1 or k == n:
		while r.next:
			s = r
			r = r.next
		s.next = None
		r.next = p.next
		p.next = None
		s.next = p
		return r
	else:
		if k > n // 2:
			k = n - k + 1
		for i in range(k - 1):
			q = p
			p = p.next
		for j in range(n - k):
			s = r
			r = r.next
		if s == p:
			q.next = r
			p.next = None
			p.next = r.next
			r.next = p
		else:
			q.next = p.next
			p.next = None
			s.next = r.next
			r.next = None
			r.next = q.next
			q.next = r
			p.next = s.next
			s.next = p
		return head


def swapkthnode(head, num, k):
	if num < k:
		return head
	prev = None
	curr = head
	curr2 = head
	prev2 = None
	t = 1
	while t < k:
		prev = curr
		curr = curr.next
		t += 1
	final = 1
	while final < num - k + 1:
		prev2 = curr2
		curr2 = curr2.next
		final += 1
	if prev != None:
		prev.next = curr2
	if prev2 != None:
		prev2.next = curr
	temp = curr.next
	curr.next = curr2.next
	curr2.next = temp
	if k == num:
		head = curr
	if k == 1:
		head = curr2
	return head


def swapkthnode(head, num, k):
	if k > num:
		return
	(c1, pre1, pre2, c2) = (head, Node(None), Node(None), head)
	for i in range(k - 1):
		pre1 = c1
		c1 = c1.next
	for i in range(num - k):
		pre2 = c2
		c2 = c2.next
	if pre1:
		pre1.next = c2
	if pre2:
		pre2.next = c1
	(c1.next, c2.next) = (c2.next, c1.next)
	if k == 1:
		head = c2
	if k == num:
		head = c1
	return head


def swapkthnode(head, num, k):
	if num < k:
		return head
	if 2 * k - 1 == num:
		return head
	x_prev = None
	x_head = head
	y_prev = None
	y_head = head
	for i in range(k - 1):
		x_prev = x_head
		x_head = x_head.next
	for i in range(num - k):
		y_prev = y_head
		y_head = y_head.next
	if y_prev:
		y_prev.next = x_head
	if x_prev:
		x_prev.next = y_head
	temp = y_head.next
	y_head.next = x_head.next
	x_head.next = temp
	if k == 1:
		head = y_head
	if k == num:
		head = x_head
	return head


def swapkthnode(head, num, k):
	pos1 = k
	pos2 = num + 1 - k
	p1 = None
	n1 = None
	p2 = None
	n1 = None
	curr = head
	curr_pos = 1
	while curr:
		if curr_pos == pos1 - 1:
			p1 = curr
		if curr_pos == pos1:
			n1 = curr
		if curr_pos == pos2 - 1:
			p2 = curr
		if curr_pos == pos2:
			n2 = curr
		curr = curr.next
		curr_pos += 1
	if n1 is None or n2 is None:
		return head
	if p1 is None:
		head = n2
	else:
		p1.next = n2
	if p2 is None:
		head = n1
	else:
		p2.next = n1
	temp = n1.next
	n1.next = n2.next
	n2.next = temp
	return head


def swapkthnode(head, num, K):
	temp = head
	temp1 = head
	if K > num:
		return head
	prev1 = head
	prev2 = head
	for i in range(1, K):
		prev1 = temp
		temp = temp.next
	for i in range(1, num - K + 1):
		prev2 = temp1
		temp1 = temp1.next
	if K != 1:
		prev1.next = temp1
	if num - K + 1 != 1:
		prev2.next = temp
	tempi = temp1.next
	temp1.next = temp.next
	temp.next = tempi
	if K == 1:
		head = temp1
	if K == num:
		head = temp
	return head


def swapkthnode(head, num, k):
	if num == 1 or k > num:
		return head
	if k == num:
		k = 1
	ptr = head
	bwp = None
	k -= 1
	while k:
		bwp = ptr
		ptr = ptr.next
		k -= 1
	bw = ptr
	fw = head
	fwp = None
	while ptr.next:
		fwp = fw
		fw = fw.next
		ptr = ptr.next
	if fw == bw:
		return head
	flag = False
	if bwp:
		bwp.next = fw
		flag = True
	if bw != fwp:
		fwp.next = bw
		bwn = bw.next
	else:
		bwn = bw
	bw.next = fw.next
	fw.next = bwn
	if not flag:
		return fw
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	if k == num - k + 1:
		return head
	beg_prev = end_prev = None
	beg = end = head
	index1 = 1
	while index1 < k:
		beg_prev = beg
		beg = beg.next
		index1 += 1
	index2 = 1
	while index2 < num - k + 1:
		end_prev = end
		end = end.next
		index2 += 1
	if beg_prev != None:
		beg_prev.next = end
	if end_prev != None:
		end_prev.next = beg
	temp = beg.next
	beg.next = end.next
	end.next = temp
	if k == 1:
		head = end
		return head
	if k == num:
		head = beg
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	if k == num - k + 1:
		return head
	beg_prev = None
	end_prev = None
	beg = head
	end = head
	index1 = 1
	for i in range(1, k):
		beg_prev = beg
		beg = beg.next
	for i in range(1, num - k + 1):
		end_prev = end
		end = end.next
	if beg_prev != None:
		beg_prev.next = end
	if end_prev != None:
		end_prev.next = beg
	temp = beg.next
	beg.next = end.next
	end.next = temp
	if k == 1:
		head = end
		return head
	if k == num:
		head = beg
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	x_prev = None
	x = head
	for i in range(k - 1):
		x_prev = x
		x = x.next
	y_prev = None
	y = head
	for i in range(n - k):
		y_prev = y
		y = y.next
	if x_prev:
		x_prev.next = y
	if y_prev:
		y_prev.next = x
	(x.next, y.next) = (y.next, x.next)
	if k == 1:
		return y
	elif k == num:
		return x
	return head


def swapkthnode(head, n, k):
	hold = n - k + 1
	if n == 1 or n < k or k == hold:
		return head
	(first, second) = (min(k, hold), max(k, hold))
	primehead = runnode = Node(None)
	runnode.next = head
	for i in range(1, first):
		runnode = runnode.next
	holdfirstprev = runnode
	holdfirst = runnode.next
	holdfirstnext = runnode.next.next
	runnode.next = runnode.next.next
	for i in range(first + 1, second):
		runnode = runnode.next
	holdsecondprev = runnode
	holdsecond = runnode.next
	holdsecondnext = runnode.next.next
	if first + 1 == second:
		holdfirstprev.next = holdsecond
		holdsecond.next = holdfirst
		holdfirst.next = holdsecondnext
	else:
		holdfirstprev.next = holdsecond
		holdsecond.next = holdfirstnext
		holdsecondprev.next = holdfirst
		holdfirst.next = holdsecondnext
	return primehead.next


def swapkthnode(head, n, k):
	listing = list()
	curr = head
	i = 1
	while curr != None:
		listing.append(curr)
		curr = curr.next
		i += 1
	primenode = newnode = Node(None)
	for i in range(1, n + 1):
		if i == k:
			newnode.next = listing[n - k]
		elif i == n - k + 1:
			newnode.next = listing[k - 1]
		else:
			newnode.next = listing[i - 1]
		newnode = newnode.next
	newnode.next = None
	return primenode.next


def swapkthnode(head, num, k):
	if k > num:
		return head
	if k == num:
		k == 1
	if k == num - k + 1:
		return head
	first = head
	firstPrv = None
	second = head
	secondPrev = None
	for i in range(0, k - 1):
		firstPrv = first
		first = first.next
	for i in range(0, num - k):
		secondPrev = second
		second = second.next
	if firstPrv == None:
		fN = first.next
		second.next = fN
		head = second
		secondPrev.next = first
		first.next = None
	elif secondPrev == None:
		sN = second.next
		first.next = sN
		head = first
		firstPrv.next = second
		second.next = None
	elif first.next == second:
		scnN = second.next
		firstPrv.next = second
		second.next = first
		first.next = scnN
	elif second.next == first:
		fN = first.next
		secondPrev.next = first
		first.next = second
		second.next = fN
	else:
		fN = first.next
		sN = second.next
		firstPrv.next = second
		second.next = fN
		secondPrev.next = first
		first.next = sN
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	target = num - k + 1
	first_pre = None
	first = None
	last_pre = None
	last = None
	temp = head
	count = 1
	if k > num // 2:
		(target, k) = (k, target)
	while temp != None:
		if count == k:
			first = temp
		if count == target:
			last = temp
		if first == None:
			first_pre = temp
		if last == None:
			last_pre = temp
		count += 1
		temp = temp.next
	if first_pre != None:
		x = last.next
		if first == last_pre:
			first_pre.next = last
			last.next = first
			first.next = x
		else:
			first_pre.next = last
			last.next = first.next
			last_pre.next = first
			first.next = x
	else:
		x = first.next
		last_pre.next = first
		first.next = last.next
		last.next = x
		head = last
	return head


def swapkthnode(head, num, k):
	start = None
	startpre = None
	endpre = None
	end = head
	ptr = head
	i = 1
	if k > num:
		return head
	while i < k:
		startpre = ptr
		ptr = ptr.next
		i += 1
	start = ptr
	while ptr.next:
		endpre = end
		ptr = ptr.next
		end = end.next
	if k == num:
		start.next = end.next
		end.next = None
		startpre.next = end
		head = start
		return head
	if k != 1:
		if start == end:
			return head
		if startpre == end:
			startpre.next = start.next
			start.next = endpre.next
			endpre.next = start
			return head
		if start == endpre:
			startpre.next = start.next
			start.next = end.next
			end.next = start
			return head
		startpre.next = start.next
		endpre.next = end.next
		end.next = startpre.next
		startpre.next = end
		start.next = endpre.next
		endpre.next = start
	if k == 1:
		end.next = head.next
		endpre.next = start
		start.next = None
		head = end
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	if k == 1 or k == num:
		temp = head
		while temp.next.next:
			temp = temp.next
		last = temp.next
		last.next = head.next
		temp.next = head
		head.next = None
		return last
	t1 = head
	t2 = head
	for e in range(k - 2):
		t1 = t1.next
	for e in range(n - k - 1):
		t2 = t2.next
	temp = t1.next
	t1.next = t2.next
	t2.next = temp
	temp = t1.next.next
	t1.next.next = t2.next.next
	t2.next.next = temp
	return head


def swapkthnode(head, num, k):
	temp = head
	prev = None
	count = 0
	if num < k:
		return
	while temp:
		count += 1
		if count == k:
			prev_l = prev
			left = temp
		if count == num - k + 1:
			prev_r = prev
			right = temp
		prev = temp
		temp = temp.next
	if prev_l is not None:
		prev_l.next = right
	if prev_r is not None:
		prev_r.next = left
	temp = left.next
	left.next = right.next
	right.next = temp
	if k == 1:
		head = right
	if k == n:
		head = left
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	s = head
	sp = None
	e = head
	ep = None
	if k == num - k + 1:
		return head
	for i in range(1, k):
		sp = s
		s = s.next
	for i in range(1, num - k + 1):
		ep = e
		e = e.next
	if sp != None:
		sp.next = e
	if ep != None:
		ep.next = s
	temp = s.next
	s.next = e.next
	e.next = temp
	if k == 1:
		return e
	if k == num:
		return s
	return head


def swapkthnode(head, n, k):
	if k > n or (n % 2 == 1 and n - k + 1 == k):
		pass
	elif k == 1 or n == k:
		tail = None
		curr = head.next
		prev = head
		while curr.next is not None:
			prev = curr
			curr = curr.next
			tail = curr
		prev.next = head
		tail.next = head.next
		head.next = None
		head = tail
	elif n % 2 == 0 and (k == n // 2 or k == n // 2 + 1):
		k = n // 2
		prev = head
		first = head.next
		second = first.next
		k -= 1
		while k > 0:
			if k == 1:
				break
			prev = first
			first = second
			second = second.next
			k -= 1
		prev.next = second
		first.next = second.next
		second.next = first
	else:
		first = None
		prev_first = None
		last = None
		prev_last = None
		curr = head
		first_counter = k
		last_counter = n - k
		while first_counter != 0:
			first_counter -= 1
			if first_counter == 1:
				prev_first = curr
				first = curr.next
				curr = curr.next
				break
			curr = curr.next
		curr = head
		while last_counter != 0:
			if last_counter == 1:
				prev_last = curr
				last = curr.next
				break
			curr = curr.next
			last_counter -= 1
		(prev_first.next, last.next, first.next, prev_last.next) = (last, first.next, last.next, first)
	return head


def swapkthnode(head, num, k):
	if n < k:
		return head
	x = head
	y = head
	prevx = None
	prevy = None
	for i in range(1, k):
		prevx = x
		x = x.next
	for i in range(1, n - k + 1):
		prevy = y
		y = y.next
	if prevx != None:
		prevx.next = y
	if prevy != None:
		prevy.next = x
	temp = x.next
	x.next = y.next
	y.next = temp
	if k == 1:
		head = y
	if k == num:
		head = x
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	(prev_beg, k_beg) = (None, head)
	for i in range(1, k):
		prev_beg = k_beg
		k_beg = k_beg.next
		if k_beg is None:
			return head
	tail = head
	(prev_end, k_end) = (None, head)
	for i in range(1, k):
		tail = tail.next
		if tail is None:
			return head
	while tail.next:
		tail = tail.next
		prev_end = k_end
		k_end = k_end.next
	nex_beg = k_beg.next if k_beg != prev_end else k_beg
	nex_end = k_end.next if k_end != prev_beg else k_end
	if prev_beg is None:
		head = k_end
	else:
		prev_beg.next = k_end
	k_end.next = nex_beg
	if prev_end is None:
		head = k_beg
	else:
		prev_end.next = k_beg
	k_beg.next = nex_end
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	k = min(k, num - k + 1)
	i = 1
	ptr = head
	if k == 1:
		while ptr.next != None:
			prev = ptr
			ptr = ptr.next
		ptr.next = head.next
		prev.next = head
		head.next = None
		head = ptr
		return head
	while ptr != None:
		prev = ptr
		ptr = ptr.next
		i += 1
		if i == k:
			op1 = ptr
			prev1 = prev
		if i == num - k + 1:
			op2 = ptr
			prev2 = prev
	prev1.next = op2
	prev2.next = op1
	temp = op1.next
	op1.next = op2.next
	op2.next = temp
	return head


class Node:

	def __init__(self, data, next=None):
		self.data = data
		self.next = next

def swapkthnode(head, num, k):
	if k > num:
		return head
	if n % 2 == 1 and n // 2 == k - 1:
		return head
	if k > n // 2:
		k = n - k + 1
	end = n - k + 1
	i = 1
	temp = head
	prev1 = None
	first = second = prev2 = prev = None
	while temp:
		if i == k:
			prev1 = prev
			first = temp
		if i == end:
			prev2 = prev
			second = temp
		prev = temp
		temp = temp.next
		i += 1
	if n % 2 == 0 and n // 2 == k:
		prev1.next = second
		temp = second.next
		second.next = first
		first.next = temp
		return head
	elif k == 1:
		prev2.next = first
		temp = first.next
		first.next = None
		second.next = temp
		return second
	else:
		prev1.next = second
		temp = second.next
		second.next = first.next
		prev2.next = first
		first.next = temp
		return head


def swapkthnode(head, num, k):
	prev1 = None
	pos = 1
	temp = head
	while pos != k:
		pos += 1
		prev1 = temp
		temp = temp.next
		if not temp:
			return
	fir = temp
	prev2 = None
	sec = head
	while temp.next:
		prev2 = sec
		temp = temp.next
		sec = sec.next
	if fir == sec:
		pass
	elif fir.next == sec:
		(prev1.next, fir.next, sec.next) = (sec, sec.next, fir)
	elif sec.next == fir:
		(prev2.next, sec.next, fir.next) = (fir, fir.next, sec)
	elif prev1 is None:
		head = sec
		prev2.next = fir
		sec.next = fir.next
		fir.next = None
	elif prev2 is None:
		head = fir
		prev1.next = sec
		fir.next = sec.next
		sec.next = None
	else:
		(prev1.next, fir.next, prev2.next, sec.next) = (sec, sec.next, fir, fir.next)
	return head


def swapkthnode(head, num, k):
	if k > num:
		return head
	if k == num - k + 1:
		return head
	beg = head
	bp = None
	end = head
	ep = None
	for i in range(1, k):
		bp = beg
		beg = beg.next
	for i in range(1, num - k + 1):
		ep = end
		end = end.next
	if bp != None:
		bp.next = end
	if ep != None:
		ep.next = beg
	temp = beg.next
	beg.next = end.next
	end.next = temp
	if k == 1:
		return end
	if k == n:
		return beg
	return head