Swap Every Kth Node in a LinkedList

by

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.

Input: A linked list, A number k.

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
Swap Evey Kth Node in a linked list

Complete Code:

public class SwapEveryKthNode {
public static void main (String[] args) throws java.lang.Exception
{
LinkedListT a = new LinkedListT();
a.addAtBegin(10);
a.addAtBegin(9);
a.addAtBegin(8);
a.addAtBegin(7);
a.addAtBegin(6);
a.addAtBegin(5);
a.addAtBegin(4);
a.addAtBegin(3);
a.addAtBegin(2);
a.addAtBegin(1);
System.out.print("Original Link List 1 : ");
a.display(a.head);
int k = 4;
Node n = a.reverseNodes(a.head, k);
System.out.println("\n Swap Every " + k + "th Node : ");
a.display(n);
}
}
class Node{
public int data;
public Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
class LinkedListT{
public Node head;
public LinkedListT(){
head=null;
}
public Node reverseNodes(Node head, int k){
int x =k;
Node ptrOne = head;
Node ptrTwo_prev = head;
Node ptrTwo = null;
if(k<2)return head;
if(ptrOne!=null){
ptrTwo = head.next;
}else return null;
while((x–2)>0){
if(ptrTwo!=null){
ptrTwo_prev = ptrTwo;
ptrTwo = ptrTwo.next;
x—;
}else{
return head;
}
}
Node newHead = ptrTwo.next;
ptrTwo_prev.next=ptrOne;
ptrTwo.next = ptrOne.next;
ptrOne.next = reverseNodes(newHead, k);
return ptrTwo;
}
public void addAtBegin(int data){
Node n = new Node(data);
n.next = head;
head = n;
}
public void display(Node head){
Node currNode = head;
while(currNode!=null){
System.out.print("->" + currNode.data);
currNode=currNode.next;
}
}
}

view raw
SwapEveryKthNode.java
hosted with ❤ by GitHub 

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

Related Posts: