123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184
#include <bits/stdc++.h>
using namespace std;
// Definition of singly linked list:
struct ListNode
{
int val;
ListNode *next;
ListNode()
{
val = 0;
next = NULL;
}
ListNode(int data1)
{
val = data1;
next = NULL;
}
ListNode(int data1, ListNode *next1)
{
val = data1;
next = next1;
}
};
class Solution {
public:
// Function to reverse a linked list
// Using the 3-pointer approach
ListNode* reverseLinkedList(ListNode *head)
{
/* Initialize 'temp' at
* head of linked list */
ListNode* temp = head;
/* Initialize pointer 'prev'
* to NULL, representing
* the previous node */
ListNode* prev = NULL;
// Continue till 'temp'
// reaches the end (NULL)
while(temp != NULL){
/* Store the next node in 'front'
* to preserve the reference */
ListNode* front = temp->next;
/* Reverse the direction of the
* current node's 'next' pointer
* to point to 'prev' */
temp->next = prev;
/* Move 'prev' to the current
* node for the next iteration */
prev = temp;
/* Move 'temp' to the 'front' node
* advancing the traversal */
temp = front;
}
// Return the new head
// of the reversed linked list
return prev;
}
// Function to get the Kth node from a
// given position in the linked list
ListNode* getKthNode(ListNode* temp, int k){
// Decrement K
// as we already start
// from the 1st node
k -= 1;
// Decrement K until it reaches the desired position
while(temp != NULL && k > 0){
// Decrement k as temp progresses
k--;
// Move to the next node
temp = temp -> next;
}
// Return the Kth node
return temp;
}
// Function to reverse nodes in groups of K
ListNode* reverseKGroup(ListNode* head, int k){
/* Initialize a temporary
* node to traverse the list */
ListNode* temp = head;
/* Initialize a pointer to track
* the last node of the previous group */
ListNode* prevLast = NULL;
// Traverse through the linked list
while(temp != NULL){
// Get the Kth node of the current group
ListNode* kThNode = getKthNode(temp, k);
/* If the Kth node is NULL
* (not a complete group) */
if(kThNode == NULL){
/* If there was a previous group,
* link the last node to the current node */
if(prevLast){
prevLast -> next = temp;
}
// Exit the loop
break;
}
/* Store the next node
* after the Kth node */
ListNode* nextNode = kThNode -> next;
/* Disconnect the Kth node
* to prepare for reversal */
kThNode -> next = NULL;
// Reverse the nodes from temp to the Kth node
reverseLinkedList(temp);
/* Adjust the head if the reversal
* starts from the head */
if(temp == head){
head = kThNode;
}else{
/* Link the last node of the previous
* group to the reversed group */
prevLast -> next = kThNode;
}
/* Update the pointer to the
* last node of the previous group */
prevLast = temp;
// Move to the next group
temp = nextNode;
}
// Return the head of the modified linked list
return head;
}
};
// Function to print the linked list
void printLinkedList(ListNode* head) {
ListNode* temp = head;
while (temp != nullptr) {
cout << temp->val << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
// Create a linked list with values 5, 4, 3, 7, 9 and 2
ListNode* head = new ListNode(5);
head->next = new ListNode(4);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(7);
head->next->next->next->next = new ListNode(9);
head->next->next->next->next->next = new ListNode(2);
// Print the original linked list
cout << "Original Linked List: ";
printLinkedList(head);
// Reverse the linked list in groups of K
Solution solution;
head = solution.reverseKGroup(head, 4);
// Print the reversed linked list
cout << "Reversed Linked List: ";
printLinkedList(head);
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177
import java.util.*;
// Definition of singly linked list:
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
class Solution {
// Function to reverse a linked list
// using the 3-pointer approach
public ListNode reverseLinkedList(ListNode head) {
/* Initialize 'temp' at
* head of linked list */
ListNode temp = head;
/* Initialize pointer 'prev'
* to NULL, representing
* the previous node */
ListNode prev = null;
// Continue till 'temp'
// reaches the end (NULL)
while (temp != null) {
/* Store the next node in 'front'
* to preserve the reference */
ListNode front = temp.next;
/* Reverse the direction of the
* current node's 'next' pointer
* to point to 'prev' */
temp.next = prev;
/* Move 'prev' to the current
* node for the next iteration */
prev = temp;
/* Move 'temp' to the 'front' node
* advancing the traversal */
temp = front;
}
// Return the new head
// of the reversed linked list
return prev;
}
// Function to get the Kth node from a
// given position in the linked list
public ListNode getKthNode(ListNode temp, int k) {
// Decrement K
// as we already start
// from the 1st node
k -= 1;
// Decrement K until it reaches the desired position
while (temp != null && k > 0) {
// Decrement k as temp progresses
k--;
// Move to the next node
temp = temp.next;
}
// Return the Kth node
return temp;
}
// Function to reverse nodes in groups of K
public ListNode reverseKGroup(ListNode head, int k) {
/* Initialize a temporary
* node to traverse the list */
ListNode temp = head;
/* Initialize a pointer to track
* the last node of the previous group */
ListNode prevLast = null;
// Traverse through the linked list
while (temp != null) {
// Get the Kth node of the current group
ListNode kThNode = getKthNode(temp, k);
/* If the Kth node is NULL
* (not a complete group) */
if (kThNode == null) {
/* If there was a previous group,
* link the last node to the current node */
if (prevLast != null) {
prevLast.next = temp;
}
// Exit the loop
break;
}
/* Store the next node
* after the Kth node */
ListNode nextNode = kThNode.next;
/* Disconnect the Kth node
* to prepare for reversal */
kThNode.next = null;
// Reverse the nodes from temp to the Kth node
reverseLinkedList(temp);
/* Adjust the head if the reversal
* starts from the head */
if (temp == head) {
head = kThNode;
} else {
/* Link the last node of the previous
* group to the reversed group */
prevLast.next = kThNode;
}
/* Update the pointer to the
* last node of the previous group */
prevLast = temp;
// Move to the next group
temp = nextNode;
}
// Return the head of the modified linked list
return head;
}
// Function to print the linked list
public static void printLinkedList(ListNode head) {
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
// Create a linked list with values 5, 4, 3, 7, 9 and 2
ListNode head = new ListNode(5);
head.next = new ListNode(4);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(7);
head.next.next.next.next = new ListNode(9);
head.next.next.next.next.next = new ListNode(2);
// Print the original linked list
System.out.print("Original Linked List: ");
printLinkedList(head);
// Reverse the linked list in groups of K
Solution solution = new Solution();
head = solution.reverseKGroup(head, 4);
// Print the reversed linked list
System.out.print("Reversed Linked List: ");
printLinkedList(head);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131
# Definition of singly linked list:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# Function to reverse a linked list
# using the 3-pointer approach
def reverseLinkedList(self, head):
""" Initialize 'temp' at
head of linked list """
temp = head
""" Initialize pointer 'prev'
to NULL, representing
the previous node """
prev = None
# Continue till 'temp'
# reaches the end (NULL)
while temp:
""" Store the next node in 'front'
to preserve the reference """
front = temp.next
""" Reverse the direction of the
current node's 'next' pointer
to point to 'prev' """
temp.next = prev
""" Move 'prev' to the current
node for the next iteration """
prev = temp
""" Move 'temp' to the 'front' node
advancing the traversal """
temp = front
# Return the new head
# of the reversed linked list
return prev
# Function to get the Kth node from a
# given position in the linked list
def getKthNode(self, temp, k):
# Decrement K
# as we already start
# from the 1st node
k -= 1
# Decrement K until it reaches the desired position
while temp and k > 0:
# Decrement k as temp progresses
k -= 1
# Move to the next node
temp = temp.next
# Return the Kth node
return temp
# Function to reverse nodes in groups of K
def reverseKGroup(self, head, k):
""" Initialize a temporary
node to traverse the list """
temp = head
""" Initialize a pointer to track
the last node of the previous group """
prevLast = None
# Traverse through the linked list
while temp:
# Get the Kth node of the current group
kThNode = self.getKthNode(temp, k)
""" If the Kth node is NULL
(not a complete group) """
if not kThNode:
""" If there was a previous group,
link the last node to the current node """
if prevLast:
prevLast.next = temp
# Exit the loop
break
""" Store the next node
after the Kth node """
nextNode = kThNode.next
""" Disconnect the Kth node
to prepare for reversal """
kThNode.next = None
# Reverse the nodes from temp to the Kth node
self.reverseLinkedList(temp)
""" Adjust the head if the reversal
starts from the head """
if temp == head:
head = kThNode
else:
""" Link the last node of the previous
group to the reversed group """
prevLast.next = kThNode
""" Update the pointer to the
last node of the previous group """
prevLast = temp
# Move to the next group
temp = nextNode
# Return the head of the modified linked list
return head
# Function to print the linked list
def printLinkedList(head):
temp = head
while temp:
print(temp.val, end=" ")
temp = temp.next
print()
# Create a linked list with values 5, 4, 3, 7, 9 and 2
head = ListNode(5)
head.next = ListNode(4)
head.next.next = ListNode(
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
reverseLinkedList(head) {
let temp = head;
let prev = null;
while (temp !== null) {
let front = temp.next;
temp.next = prev;
prev = temp;
temp = front;
}
return prev;
}
getKthNode(temp, k) {
k -= 1;
while (temp !== null && k > 0) {
k--;
temp = temp.next;
}
return temp;
}
reverseKGroup(head, k) {
let temp = head;
let prevLast = null;
while (temp !== null) {
let kThNode = this.getKthNode(temp, k);
if (kThNode === null) {
if (prevLast !== null) {
prevLast.next = temp;
}
break;
}
let nextNode = kThNode.next;
kThNode.next = null;
this.reverseLinkedList(temp);
if (temp === head) {
head = kThNode;
} else {
prevLast.next = kThNode;
}
prevLast = temp;
temp = nextNode;
}
return head;
}
}
function printLinkedList(head) {
let temp = head;
while (temp !== null) {
process.stdout.write(temp.val + " ");
temp = temp.next;
}
console.log();
}
let head = new ListNode(5);
head.next = new ListNode(4);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(7);
head.next.next.next.next = new ListNode(9);
head.next.next.next.next.next = new ListNode(2);
process.stdout.write("Original Linked List: ");
printLinkedList(head);
const solution = new Solution();
head = solution.reverseKGroup(head, 4);
process.stdout.write("Reversed Linked List: ");
printLinkedList(head);
