# 算法设计：单链表中的交替奇偶节点

2021年3月17日15:16:52 发表评论 337 次浏览

## 本文概述

``````Input : 11 -> 20 -> 40 -> 55 -> 77 -> 80 -> NULL
Output : 11 -> 20 -> 55 -> 40 -> 77 -> 80 -> NULL
20, 40, 80 occur in even positions and 11, 55, 77
occur in odd positions.

Input : 10 -> 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> NULL
Output : 1 -> 10 -> 3 -> 2 -> 5 -> 6 -> 7 -> 8 -> NULL
1, 3, 5, 7 occur in odd positions and 10, 2, 6, 8 occur
at even positions in the list``````

## C ++

``````// CPP program to rearrange nodes
// as alternate odd even nodes in
#include <bits/stdc++.h>
using namespace std;

// Structure node
struct Node {
int data;
struct Node* next;
};

// A utility function to print
void printList( struct Node* node)
{
while (node != NULL) {
cout << node->data << " " ;
node = node->next;
}
cout << endl;
}

// Function to create newNode
Node* newNode( int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}

// Function to insert at beginning
{
Node* temp = newNode(val);
}

// Function to rearrange the
// odd and even nodes
{
stack<Node*> odd;
stack<Node*> even;
int i = 1;

if (head->data % 2 != 0 && i % 2 == 0) {

// Odd Value in Even Position
// Add pointer to current node
// in odd stack
}

else if (head->data % 2 == 0 && i % 2 != 0) {

// Even Value in Odd Position
// Add pointer to current node
// in even stack
}

i++;
}

while (!odd.empty() && !even.empty()) {

// Swap Data at the top of two stacks
swap(odd.top()->data, even.top()->data);
odd.pop();
even.pop();
}
}

// Driver code
int main()
{

cout << "Linked List:" << endl;

cout << "Linked List after "
<< "Rearranging:" << endl;

return 0;
}``````

## Java

``````// Java program to rearrange nodes
// as alternate odd even nodes in
import java.util.*;

class GFG
{

// class node
static class Node
{
int data;
Node next;
}

// A utility function to print
static void printList(Node node)
{
while (node != null )
{
System.out.print(node.data + " " );
node = node.next;
}
System.out.println();
}

// Function to create newNode
static Node newNode( int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null ;
return temp;
}

// Function to insert at beginning
static Node insertBeg(Node head, int val)
{
Node temp = newNode(val);
}

// Function to rearrange the
// odd and even nodes
{
Stack<Node> odd= new Stack<Node>();
Stack<Node> even= new Stack<Node>();
int i = 1 ;

while (head != null ) {

if (head.data % 2 != 0 && i % 2 == 0 )
{

// Odd Value in Even Position
// Add pointer to current node
// in odd stack
}

else if (head.data % 2 == 0 && i % 2 != 0 )
{

// Even Value in Odd Position
// Add pointer to current node
// in even stack
}

i++;
}

while (odd.size() > 0 && even.size() > 0 )
{

// Swap Data at the top of two stacks
int k=odd.peek().data;
odd.peek().data=even.peek().data;
even.peek().data=k;
odd.pop();
even.pop();
}
}

// Driver code
public static void main(String args[])
{
Node head = newNode( 8 );

System.out.println( "Linked List after " +
"Rearranging:" );
}
}

// This contributed by Arnab Kundu``````

## python

``````# Python program to rearrange nodes
# as alternate odd even nodes in

class Node:

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

# A utility function to print
def printList( node):

while (node ! = None ) :
print (node.data , end = " " )
node = node. next

print ( "\n" )

# Function to create newNode
def newNode(key):

temp = Node( 0 )
temp.data = key
temp. next = None
return temp

# Function to insert at beginning

temp = newNode(val)

# Function to rearrange the
# odd and even nodes

odd = []
even = []
i = 1

while (head ! = None ):

if (head.data % 2 ! = 0 and i % 2 = = 0 ):

# Odd Value in Even Position
# Add pointer to current node
# in odd stack

elif (head.data % 2 = = 0 and i % 2 ! = 0 ):

# Even Value in Odd Position
# Add pointer to current node
# in even stack

i = i + 1

while ( len (odd) ! = 0 and len (even) ! = 0 ) :

# Swap Data at the top of two stacks
odd[ - 1 ].data, even[ - 1 ].data = even[ - 1 ].data, odd[ - 1 ].data
odd.pop()
even.pop()

# Driver code

print ( "Linked List after " , "Rearranging:" )

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

## C#

``````// C# program to rearrange nodes
// as alternate odd even nodes in
using System;
using System.Collections.Generic;

class GFG
{

// class node
public class Node
{
public int data;
public Node next;
}

// A utility function to print
static void printList(Node node)
{
while (node != null )
{
Console.Write(node.data + " " );
node = node.next;
}
Console.WriteLine();
}

// Function to create newNode
static Node newNode( int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null ;
return temp;
}

// Function to insert at beginning
static Node insertBeg(Node head, int val)
{
Node temp = newNode(val);
}

// Function to rearrange the
// odd and even nodes
{
Stack<Node> odd = new Stack<Node>();
Stack<Node> even = new Stack<Node>();
int i = 1;

{

if (head.data % 2 != 0 && i % 2 == 0)
{

// Odd Value in Even Position
// Add pointer to current node
// in odd stack
}

else if (head.data % 2 == 0 && i % 2 != 0)
{

// Even Value in Odd Position
// Add pointer to current node
// in even stack
}

i++;
}

while (odd.Count > 0 && even.Count > 0)
{

// Swap Data at the top of two stacks
int k=odd.Peek().data;
odd.Peek().data=even.Peek().data;
even.Peek().data=k;
odd.Pop();
even.Pop();
}
}

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

Console.WriteLine( "Linked List after " +
"Rearranging:" );
}
}

// This code has been contributed by 29AjayKumar``````

``````Linked List:
1 2 3 5 6 7 8
1 2 3 6 5 8 7``````

1. 隔离列表中的奇数和偶数值。此后, 所有奇数值将一起出现, 随后是所有偶数值。
2. 将列表分为两个列表, 奇数和偶数。
3. 将偶数列表合并为奇数列表
``````REARRANGE (HEAD)
Step 1: Traverse the list using NODE TEMP.
If TEMP is odd
Add TEMP to the beginning of the List
[END OF IF]
[END OF TRAVERSAL]
Step 2: Set TEMP to 2nd element of LIST.
Step 3: Set PREV_TEMP to 1st element of List
Step 4: Traverse using node TEMP as long as an even
node is not encountered.
PREV_TEMP = TEMP, TEMP = TEMP->NEXT
[END OF TRAVERSAL]
Step 5: Set EVEN to TEMP. Set PREV_TEMP->NEXT to NULL
Step 6: I = HEAD, J = EVEN
Step 7: Repeat while I != NULL and J != NULL
Store next nodes of I and J in K and L
K = I->NEXT, L = J->NEXT
I->NEXT = J, J->NEXT = K, PTR = J
I = K and J = L
[END OF LOOP]
Step 8: if I == NULL
PTR->NEXT = J
[END of IF]
Step 9: End``````

## C ++

``````// Cpp program to rearrange nodes
// as alternate odd even nodes in
#include <bits/stdc++.h>
using namespace std;

// Structure node
struct Node {
int data;
struct Node* next;
};

// A utility function to print
void printList( struct Node* node)
{
while (node != NULL) {
cout << node->data << " " ;
node = node->next;
}
cout << endl;
}

// Function to create newNode
Node* newNode( int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}

// Function to insert at beginning
{
Node* temp = newNode(val);
}

// Function to rearrange the
// odd and even nodes
{
// Step 1: Segregate even and odd nodes
// Step 2: Split odd and even lists
// Step 3: Merge even list into odd list
Node* even;
Node *temp, *prev_temp;
Node *i, *j, *k, *l, *ptr;

// Step 1: Segregate Odd and Even Nodes

while (temp != nullptr) {

// Backup next pointer of temp
Node* x = temp->next;

// If temp is odd move the node
// to beginning of list
if (temp->data % 2 != 0) {
prev_temp->next = x;
}
else {
prev_temp = temp;
}

temp = x;
}

// Step 2
// Split the List into Odd and even

while (temp != nullptr && temp->data % 2 != 0) {
prev_temp = temp;
temp = temp->next;
}

even = temp;

// End the odd List (Make last node null)
prev_temp->next = nullptr;

// Step 3:
// Merge Even List into odd
j = even;

while (j != nullptr && i != nullptr) {

// While both lists are not
// exhausted Backup next
// pointers of i and j
k = i->next;
l = j->next;

i->next = j;
j->next = k;

// ptr points to the latest node added
ptr = j;

// Advance i and j pointers
i = k;
j = l;
}

if (i == nullptr) {

// Odd list exhausts before even, // append remainder of even list to odd.
ptr->next = j;
}

// The case where even list exhausts before
// odd list is automatically handled since we
// merge the even list into the odd list
}

// Driver Code
int main()
{

cout << "Linked List:" << endl;
cout << "Rearranged List" << endl;
}``````

## Java

``````// Java program to rearrange nodes
// as alternate odd even nodes in
class GFG
{

// Structure node
static class Node
{
int data;
Node next;
};

// A utility function to print
static void printList(Node node)
{
while (node != null )
{
System.out.print(node.data + " " );
node = node.next;
}
System.out.println();
}

// Function to create newNode
static Node newNode( int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null ;
return temp;
}

// Function to insert at beginning
static Node insertBeg(Node head, int val)
{
Node temp = newNode(val);
}

// Function to rearrange the
// odd and even nodes
{
// Step 1: Segregate even and odd nodes
// Step 2: Split odd and even lists
// Step 3: Merge even list into odd list
Node even;
Node temp, prev_temp;
Node i, j, k, l, ptr= null ;

// Step 1: Segregate Odd and Even Nodes

while (temp != null )
{

// Backup next pointer of temp
Node x = temp.next;

// If temp is odd move the node
// to beginning of list
if (temp.data % 2 != 0 )
{
prev_temp.next = x;
}
else
{
prev_temp = temp;
}

temp = x;
}

// Step 2
// Split the List into Odd and even

while (temp != null && temp.data % 2 != 0 )
{
prev_temp = temp;
temp = temp.next;
}

even = temp;

// End the odd List (Make last node null)
prev_temp.next = null ;

// Step 3:
// Merge Even List into odd
j = even;

while (j != null && i != null )
{

// While both lists are not
// exhausted Backup next
// pointers of i and j
k = i.next;
l = j.next;

i.next = j;
j.next = k;

// ptr points to the latest node added
ptr = j;

// Advance i and j pointers
i = k;
j = l;
}

if (i == null )
{

// Odd list exhausts before even, // append remainder of even list to odd.
ptr.next = j;
}

// The case where even list exhausts before
// odd list is automatically handled since we
// merge the even list into the odd list
}

// Driver Code
public static void main(String args[])
{
Node head = newNode( 8 );

System.out.println( "Rearranged List" );
}
}

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

## Python3

``````# Python3 program to rearrange nodes
# as alternate odd even nodes in

# Structure node
class Node :

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

# A utility function to print
def printList(node) :
while (node ! = None ) :
print (node.data, end = " " )
node = node. next

print ( " " )

# Function to create newNode
def newNode( key) :
temp = Node()
temp.data = key
temp. next = None
return temp

# Function to insert at beginning
temp = newNode(val)

# Function to rearrange the
# odd and even nodes

# Step 1: Segregate even and odd nodes
# Step 2: Split odd and even lists
# Step 3: Merge even list into odd list
even = None
temp = None
prev_temp = None
i = None
j = None
k = None
l = None
ptr = None

# Step 1: Segregate Odd and Even Nodes

while (temp ! = None ) :

# Backup next pointer of temp
x = temp. next

# If temp is odd move the node
# to beginning of list
if (temp.data % 2 ! = 0 ) :

prev_temp. next = x

else :

prev_temp = temp

temp = x

# Step 2
# Split the List into Odd and even

while (temp ! = None and temp.data % 2 ! = 0 ) :
prev_temp = temp
temp = temp. next

even = temp

# End the odd List (Make last node None)
prev_temp. next = None

# Step 3:
# Merge Even List into odd
j = even

while (j ! = None and i ! = None ):

# While both lists are not
# exhausted Backup next
# pointers of i and j
k = i. next
l = j. next

i. next = j
j. next = k

# ptr points to the latest node added
ptr = j

# Advance i and j pointers
i = k
j = l

if (i = = None ):

# Odd list exhausts before even, # append remainder of even list to odd.
ptr. next = j

# The case where even list exhausts before
# odd list is automatically handled since we
# merge the even list into the odd list

# Driver Code

print ( "Rearranged List" )

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

## C#

``````// C# program to rearrange nodes
// as alternate odd even nodes in
using System;

class GFG
{

// Structure node
public class Node
{
public int data;
public Node next;
};

// A utility function to print
static void printList(Node node)
{
while (node != null )
{
Console.Write(node.data + " " );
node = node.next;
}
Console.WriteLine();
}

// Function to create newNode
static Node newNode( int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null ;
return temp;
}

// Function to insert at beginning
static Node insertBeg(Node head, int val)
{
Node temp = newNode(val);
}

// Function to rearrange the
// odd and even nodes
{
// Step 1: Segregate even and odd nodes
// Step 2: Split odd and even lists
// Step 3: Merge even list into odd list
Node even;
Node temp, prev_temp;
Node i, j, k, l, ptr= null ;

// Step 1: Segregate Odd and Even Nodes

while (temp != null )
{

// Backup next pointer of temp
Node x = temp.next;

// If temp is odd move the node
// to beginning of list
if (temp.data % 2 != 0)
{
prev_temp.next = x;
}
else
{
prev_temp = temp;
}

temp = x;
}

// Step 2
// Split the List into Odd and even

while (temp != null && temp.data % 2 != 0)
{
prev_temp = temp;
temp = temp.next;
}

even = temp;

// End the odd List (Make last node null)
prev_temp.next = null ;

// Step 3:
// Merge Even List into odd
j = even;

while (j != null && i != null )
{

// While both lists are not
// exhausted Backup next
// pointers of i and j
k = i.next;
l = j.next;

i.next = j;
j.next = k;

// ptr points to the latest node added
ptr = j;

// Advance i and j pointers
i = k;
j = l;
}

if (i == null )
{

// Odd list exhausts before even, // append remainder of even list to odd.
ptr.next = j;
}

// The case where even list exhausts before
// odd list is automatically handled since we
// merge the even list into the odd list
}

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

Console.WriteLine( "Rearranged List" );
}
}

// This code is contributed by Rajput-Ji``````

``````Linked List:
10 2 1 5 3 6 7 8
Rearranged List
7 10 3 2 5 6 1 8``````

O(1) 