This post is completed by 2 users

  • 0
Add to List
Medium

30. Swap Every Kth Node in a LinkedList

Objective: Given a linked list, swap every kth node in that. If at the end of the list remaining nodes are less than k, leave them untouched.

Example:

Input : -1-2-3-4-5-6-7-8-9-10 , K = 4
Output: -4-2-3-1-8-6-7-5-9-10

Approach:

  • Take 3 Pointers, ptrOne, ptrTwo and ptrTwo_prev.
  • ptrOne and ptrTwo_prev points at head node.
  • ptrTwo points at next node of ptrTwo_prev.
  • Move the ptrTwo and ptrTwo_prev k-2 times, since we need one pointer each at both ends for swapping so move pointers only k-2 times.
  • Create another pointer, newHead and point it to ptrTwo.next.
  • Now we have ptrOne at head and ptrTwo at kth position, swap them with the help of ptrTwo_prev.
  • This function will returns the head.
  • Now make a recursive call with newHead.

ptrOne.next = reverseNodes(newHead, k);

Swap Evey Kth Node in a linked list

Output:

  Original Link List 1 : -1-2-3-4-5-6-7-8-9-10
Swap Every 4th Node :-4-2-3-1-8-6-7-5-9-10