# 算法设计：在一个单链表中反向交替K个节点

2021年3月14日14:27:55 发表评论 673 次浏览

## 本文概述

``````Inputs:   1->2->3->4->5->6->7->8->9->NULL and k = 3
Output:   3->2->1->4->5->6->9->8->7->NULL.``````

## 推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

``````kAltReverse(struct node *head, int k)
1)  Reverse first k nodes.
2)  In the modified list head points to the kth node.  So change next
3)  Move the current pointer to skip next k nodes.
4)  Call the kAltReverse() recursively for rest of the n - 2k nodes.
5)  Return new head of the list.``````

## C ++

``````// C++ program to reverse alternate
// k nodes in a linked list
#include <bits/stdc++.h>
using namespace std;

class Node
{
public :
int data;
Node* next;
};

/* Reverses alternate k nodes and
returns the pointer to the new head node */
{
Node* next;
Node* prev = NULL;
int count = 0;

/*1) reverse first k nodes of the linked list */
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}

/* 2) Now head points to the kth node.
So change next  of head to (k+1)th node*/

/* 3) We do not want to reverse next k
nodes. So move the current
pointer to skip next k nodes */
count = 0;
while (count < k-1 && current != NULL )
{
current = current->next;
count++;
}

/* 4) Recursively call for the list
starting from current->next. And make
rest of the list as next of first node */
if (current != NULL)
current->next = kAltReverse(current->next, k);

/* 5) prev is new head of the input list */
return prev;
}

/* UTILITY FUNCTIONS */
/* Function to push a node */
{
/* allocate node */
Node* new_node = new Node();

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print linked list */
void printList(Node *node)
{
int count = 0;
while (node != NULL)
{
cout<<node->data<< " " ;
node = node->next;
count++;
}
}

/* Driver code*/
int main( void )
{
int i;

// create a list 1->2->3->4->5...... ->20
for (i = 20; i > 0; i--)

cout<< "Given linked list \n" ;

cout<< "\n Modified Linked list \n" ;
return (0);
}

// This code is contributed by rathbhupendra``````

## C

``````#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node* next;
};

/* Reverses alternate k nodes and
returns the pointer to the new head node */
struct Node *kAltReverse( struct Node *head, int k)
{
struct Node* next;
struct Node* prev = NULL;
int count = 0;

/*1) reverse first k nodes of the linked list */
while (current != NULL && count < k)
{
next  = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}

/* 2) Now head points to the kth node.  So change next

/* 3) We do not want to reverse next k nodes. So move the current
pointer to skip next k nodes */
count = 0;
while (count < k-1 && current != NULL )
{
current = current->next;
count++;
}

/* 4) Recursively call for the list starting from current->next.
And make rest of the list as next of first node */
if (current !=  NULL)
current->next = kAltReverse(current->next, k);

/* 5) prev is new head of the input list */
return prev;
}

/* UTILITY FUNCTIONS */
/* Function to push a node */
void push( struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
( struct Node*) malloc ( sizeof ( struct Node));

/* put in the data  */
new_node->data  = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print linked list */
void printList( struct Node *node)
{
int count = 0;
while (node != NULL)
{
printf ( "%d  " , node->data);
node = node->next;
count++;
}
}

/* Driver program to test above function*/
int main( void )
{
int i;
// create a list 1->2->3->4->5...... ->20
for (i = 20; i > 0; i--)

printf ( "\n Given linked list \n" );

printf ( "\n Modified Linked list \n" );

getchar ();
return (0);
}``````

## Java

``````// Java program to reverse alternate k nodes in a linked list

class Node {

int data;
Node next;

Node( int d) {
data = d;
next = null ;
}
}

/* Reverses alternate k nodes and
returns the pointer to the new head node */
Node kAltReverse(Node node, int k) {
Node current = node;
Node next = null , prev = null ;
int count = 0 ;

/*1) reverse first k nodes of the linked list */
while (current != null && count < k) {
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}

/* 2) Now head points to the kth node.  So change next
if (node != null ) {
node.next = current;
}

/* 3) We do not want to reverse next k nodes. So move the current
pointer to skip next k nodes */
count = 0 ;
while (count < k - 1 && current != null ) {
current = current.next;
count++;
}

/* 4) Recursively call for the list starting from current->next.
And make rest of the list as next of first node */
if (current != null ) {
current.next = kAltReverse(current.next, k);
}

/* 5) prev is new head of the input list */
return prev;
}

void printList(Node node) {
while (node != null ) {
System.out.print(node.data + " " );
node = node.next;
}
}

void push( int newdata) {
Node mynode = new Node(newdata);
}

public static void main(String[] args) {

for ( int i = 20 ; i > 0 ; i--) {
list.push(i);
}
System.out.println( "Given Linked List :" );
System.out.println( "" );
System.out.println( "Modified Linked List :" );

}
}

// This code has been contributed by Mayank Jaiswal``````

## Python3

``````# Python3 program to reverse alternate
# k nodes in a linked list
import math

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

# Reverses alternate k nodes and
#returns the poer to the new head node
next = None
prev = None
count = 0

#1) reverse first k nodes of the linked list
while (current ! = None and count < k) :
next = current. next
current. next = prev
prev = current
current = next
count = count + 1 ;

# 2) Now head pos to the kth node.
# So change next of head to (k+1)th node
if (head ! = None ):

# 3) We do not want to reverse next k
# nodes. So move the current
# poer to skip next k nodes
count = 0
while (count < k - 1 and current ! = None ):
current = current. next
count = count + 1

# 4) Recursively call for the list
# starting from current.next. And make
# rest of the list as next of first node
if (current ! = None ):
current. next = kAltReverse(current. next , k)

# 5) prev is new head of the input list
return prev

# UTILITY FUNCTIONS
# Function to push a node

# allocate node
new_node = Node(new_data)

# put in the data
# new_node.data = new_data

# link the old list off the new node

# move the head to po to the new node

# Function to print linked list
def prList(node):
count = 0
while (node ! = None ):
print (node.data, end = " " )
node = node. next
count = count + 1

# Driver code
if __name__ = = '__main__' :

# create a list 1.2.3.4.5...... .20
for i in range ( 20 , 0 , - 1 ):

print ( "Given linked list " )

print ( "\nModified Linked list" )

# This code is contributed by Srathore``````

## C#

``````// C# program to reverse alternate
// k nodes in a linked list
using System;
{

public class Node
{

public int data;
public Node next;

public Node( int d)
{
data = d;
next = null ;
}
}

/* Reverses alternate k nodes and
returns the pointer to the new head node */
Node kAltReverse(Node node, int k)
{
Node current = node;
Node next = null , prev = null ;
int count = 0;

/*1) reverse first k nodes of the linked list */
while (current != null && count < k)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}

/* 2) Now head points to the kth
node. So change next
if (node != null )
{
node.next = current;
}

/* 3) We do not want to reverse
next k nodes. So move the current
pointer to skip next k nodes */
count = 0;
while (count < k - 1 && current != null )
{
current = current.next;
count++;
}

/* 4) Recursively call for the
list starting from current->next.
And make rest of the list as
next of first node */
if (current != null )
{
current.next = kAltReverse(current.next, k);
}

/* 5) prev is new head of the input list */
return prev;
}

void printList(Node node)
{
while (node != null )
{
Console.Write(node.data + " " );
node = node.next;
}
}

void push( int newdata)
{
Node mynode = new Node(newdata);
}

// Driver code
public static void Main(String []args)
{

for ( int i = 20; i > 0; i--)
{
list.push(i);
}
Console.WriteLine( "Given Linked List :" );
Console.WriteLine( "" );
Console.WriteLine( "Modified Linked List :" );
}
}

// This code has been contributed by Arnab Kundu``````

``````Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19``````

``````_kAltReverse(struct node *head, int k, bool b)
1)  If b is true, then reverse first k nodes.
2)  If b is false, then move the pointer k nodes ahead.
3)  Call the kAltReverse() recursively for rest of the n - k nodes and link
rest of the modified list with end of first k nodes.
4)  Return new head of the list.``````

## C ++

``````#include <bits/stdc++.h>
using namespace std;

class node
{
public :
int data;
node* next;
};

/* Helper function for kAltReverse() */
node * _kAltReverse(node *node, int k, bool b);

/* Alternatively reverses the given linked list
in groups of given size k. */
{
}

/* Helper function for kAltReverse().
It reverses k nodes of the list only if
the third parameter b is passed as true, otherwise moves the pointer k nodes ahead
and recursively calls iteself */
node * _kAltReverse(node *Node, int k, bool b)
{
if (Node == NULL)
return NULL;

int count = 1;
node *prev = NULL;
node *current = Node;
node *next;

/* The loop serves two purposes
1) If b is true, then it reverses the k nodes
2) If b is false, then it moves the current pointer */
while (current != NULL && count <= k)
{
next = current->next;

/* Reverse the nodes only if b is true*/
if (b == true )
current->next = prev;

prev = current;
current = next;
count++;
}

/* 3) If b is true, then node is the kth node.
So attach rest of the list after node.
4) After attaching, return the new head */
if (b == true )
{
Node->next = _kAltReverse(current, k, !b);
return prev;
}

/* If b is not true, then attach
rest of the list after prev.
So attach rest of the list after prev */
else
{
prev->next = _kAltReverse(current, k, !b);
return Node;
}
}

/* UTILITY FUNCTIONS */
/* Function to push a node */
{
/* allocate node */
node* new_node = new node();

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print linked list */
void printList(node *node)
{
int count = 0;
while (node != NULL)
{
cout << node->data << " " ;
node = node->next;
count++;
}
}

// Driver Code
int main( void )
{
int i;

// create a list 1->2->3->4->5...... ->20
for (i = 20; i > 0; i--)

cout << "Given linked list \n" ;

cout << "\nModified Linked list \n" ;
return (0);
}

// This code is contributed by rathbhupendra``````

## C

``````#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node* next;
};

/* Helper function for kAltReverse() */
struct node * _kAltReverse( struct node *node, int k, bool b);

/* Alternatively reverses the given linked list in groups of
given size k. */
struct node *kAltReverse( struct node *head, int k)
{
}

/*  Helper function for kAltReverse().  It reverses k nodes of the list only if
the third parameter b is passed as true, otherwise moves the pointer k
nodes ahead and recursively calls iteself  */
struct node * _kAltReverse( struct node *node, int k, bool b)
{
if (node == NULL)
return NULL;

int count = 1;
struct node *prev = NULL;
struct node  *current = node;
struct node *next;

/* The loop serves two purposes
1) If b is true, then it reverses the k nodes
2) If b is false, then it moves the current pointer */
while (current != NULL && count <= k)
{
next = current->next;

/* Reverse the nodes only if b is true*/
if (b == true )
current->next = prev;

prev = current;
current = next;
count++;
}

/* 3) If b is true, then node is the kth node.
So attach rest of the list after node.
4) After attaching, return the new head */
if (b == true )
{
node->next = _kAltReverse(current, k, !b);
return prev;
}

/* If b is not true, then attach rest of the list after prev.
So attach rest of the list after prev */
else
{
prev->next = _kAltReverse(current, k, !b);
return node;
}
}

/* UTILITY FUNCTIONS */
/* Function to push a node */
void push( struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
( struct node*) malloc ( sizeof ( struct node));

/* put in the data  */
new_node->data  = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print linked list */
void printList( struct node *node)
{
int count = 0;
while (node != NULL)
{
printf ( "%d  " , node->data);
node = node->next;
count++;
}
}

/* Driver program to test above function*/
int main( void )
{
int i;

// create a list 1->2->3->4->5...... ->20
for (i = 20; i > 0; i--)

printf ( "\n Given linked list \n" );

printf ( "\n Modified Linked list \n" );

getchar ();
return (0);
}``````

## Java

``````// Java program to reverse alternate k nodes in a linked list

class Node {

int data;
Node next;

Node( int d) {
data = d;
next = null ;
}
}

/* Alternatively reverses the given linked list in groups of
given size k. */
Node kAltReverse(Node head, int k) {
}

/*  Helper function for kAltReverse().  It reverses k nodes of the list only if
the third parameter b is passed as true, otherwise moves the pointer k
nodes ahead and recursively calls iteself  */
Node _kAltReverse(Node node, int k, boolean b) {
if (node == null ) {
return null ;
}

int count = 1 ;
Node prev = null ;
Node current = node;
Node next = null ;

/* The loop serves two purposes
1) If b is true, then it reverses the k nodes
2) If b is false, then it moves the current pointer */
while (current != null && count <= k) {
next = current.next;

/* Reverse the nodes only if b is true*/
if (b == true ) {
current.next = prev;
}

prev = current;
current = next;
count++;
}

/* 3) If b is true, then node is the kth node.
So attach rest of the list after node.
4) After attaching, return the new head */
if (b == true ) {
node.next = _kAltReverse(current, k, !b);
return prev;
} /* If b is not true, then attach rest of the list after prev.
So attach rest of the list after prev */ else {
prev.next = _kAltReverse(current, k, !b);
return node;
}
}

void printList(Node node) {
while (node != null ) {
System.out.print(node.data + " " );
node = node.next;
}
}

void push( int newdata) {
Node mynode = new Node(newdata);
}

public static void main(String[] args) {

for ( int i = 20 ; i > 0 ; i--) {
list.push(i);
}
System.out.println( "Given Linked List :" );
System.out.println( "" );
System.out.println( "Modified Linked List :" );

}
}

// This code has been contributed by Mayank Jaiswal``````

## python

``````# Python code for above algorithm

class node:

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

# function to insert a node at the
# beginning of the linked list

# allocate node
new_node = node( 0 )

# put in the data
new_node.data = new_data

# link the old list to the new node

# move the head to point to the new node

""" Alternatively reverses the given linked list
in groups of given size k. """

""" Helper function for kAltReverse().
It reverses k nodes of the list only if
the third parameter b is passed as True, otherwise moves the pointer k nodes ahead
and recursively calls iteself """
def _kAltReverse(Node, k, b) :

if (Node = = None ) :
return None

count = 1
prev = None
current = Node
next = None

""" The loop serves two purposes
1) If b is True, then it reverses the k nodes
2) If b is false, then it moves the current pointer """
while (current ! = None and count < = k) :

next = current. next

""" Reverse the nodes only if b is True"""
if (b = = True ) :
current. next = prev

prev = current
current = next
count = count + 1

""" 3) If b is True, then node is the kth node.
So attach rest of the list after node.
4) After attaching, return the new head """
if (b = = True ) :

Node. next = _kAltReverse(current, k, not b)
return prev

else :
""" If b is not True, then attach
rest of the list after prev.
So attach rest of the list after prev """
prev. next = _kAltReverse(current, k, not b)
return Node

""" Function to print linked list """
def printList(node) :

count = 0
while (node ! = None ) :

print ( node.data, end = " " )
node = node. next
count = count + 1

# Driver Code

i = 20

# create a list 1->2->3->4->5...... ->20
while (i > 0 ):
i = i - 1

print ( "Given linked list " )

print ( "\nModified Linked list " )

# This code is contributed by Arnab Kundu``````

## C#

``````// C# Program for converting
using System;

{

public class Node
{

public int data;
public Node next;

public Node( int d)
{
data = d;
next = null ;
}
}

/* Reverses alternate k nodes and
returns the pointer to the new head node */
Node kAltReverse(Node node, int k)
{
Node current = node;
Node next = null , prev = null ;
int count = 0;

/*1) reverse first k nodes of the linked list */
while (current != null && count < k)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}

/* 2) Now head points to the kth node.
So change next of head to (k+1)th node*/
if (node != null )
{
node.next = current;
}

/* 3) We do not want to reverse next
k nodes. So move the current
pointer to skip next k nodes */
count = 0;
while (count < k - 1 && current != null )
{
current = current.next;
count++;
}

/* 4) Recursively call for the list
starting from current->next. And make
rest of the list as next of first node */
if (current != null )
{
current.next = kAltReverse(current.next, k);
}

/* 5) prev is new head of the input list */
return prev;
}

void printList(Node node)
{
while (node != null )
{
Console.Write(node.data + " " );
node = node.next;
}
}

void push( int newdata)
{
Node mynode = new Node(newdata);
}

public static void Main(String[] args)
{

for ( int i = 20; i > 0; i--)
{
list.push(i);
}
Console.WriteLine( "Given Linked List :" );
Console.WriteLine( "" );
Console.WriteLine( "Modified Linked List :" );
}
}

// This code is contributed 29AjayKumar``````

``````Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20