本文概述

• 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
• C ++
• Java
• python
• C#
• C ++
• Java
• Python3
• C#

给定一个单链表, 请重新排列该列表, 以使偶数和奇数节点在列表中交替出现。
这种重新排列有两种可能的形式。如果第一个数据为奇数, 则第二个节点必须为偶数。第三个节点必须是奇数, 依此类推。请注意, 在第一个节点为偶数, 第二个奇数, 第三个偶数等的情况下, 还有另一种安排。
例子：

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

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。方法1(简单)
在此方法中, 我们创建两个堆栈-奇数和偶数。我们遍历该列表, 当我们在奇数位置遇到偶数节点时, 会将其地址推送到偶数堆栈。如果我们在偶数位置遇到一个奇数节点, 则将该节点的地址压入奇数堆栈。
遍历列表后, 我们只需弹出两个堆栈顶部的节点并交换它们的数据。我们一直重复此步骤, 直到堆栈变空。

【算法设计（单链表中的交替奇偶节点）】步骤1：创建两个堆栈, 奇数和偶数。这些堆栈会将指针存储到列表中的节点。步骤2：使用变量current, 从头到尾遍历列表。重复以下步骤3-4的步骤：步骤3：如果当前节点为偶数并且出现在一个奇数位置, 则将该节点的地址推入堆栈偶数步骤4：如果当前节点为奇数并且出现在一个偶数位置, 则将该节点的地址推至堆叠奇数。 [遍历结束]步骤5：两个堆栈的大小将相同。当两个堆栈都不为空时, 交换两个堆栈顶部的节点, 并从各自的堆栈弹出两个节点。步骤6：现在重新排列了列表。停

C ++

// CPP program to rearrange nodes // as alternate odd even nodes in // a Singly Linked List #include < bits/stdc++.h> using namespace std; // Structure node struct Node { int data; struct Node* next; }; // A utility function to print // linked list void printList( struct Node* node) { while (node != NULL) { cout < < node-> data < < " " ; node = node-> next; } cout < < endl; }// Function to create newNode // in a linkedlist Node* newNode( int key) { Node* temp = new Node; temp-> data = https://www.lsbin.com/key; temp-> next = NULL; return temp; }// Function to insert at beginning Node* insertBeg(Node* head, int val) { Node* temp = newNode(val); temp-> next = head; head = temp; return head; }// Function to rearrange the // odd and even nodes void rearrangeOddEven(Node* head) { stack< Node*> odd; stack< Node*> even; int i = 1; while (head != nullptr) {if (head-> data % 2 != 0 & & i % 2 == 0) {// Odd Value in Even Position // Add pointer to current node // in odd stack odd.push(head); }else if (head-> data % 2 == 0 & & i % 2 != 0) {// Even Value in Odd Position // Add pointer to current node // in even stack even.push(head); }head = head-> next; 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() { Node* head = newNode(8); head = insertBeg(head, 7); head = insertBeg(head, 6); head = insertBeg(head, 5); head = insertBeg(head, 3); head = insertBeg(head, 2); head = insertBeg(head, 1); cout < <"Linked List:" < < endl; printList(head); rearrangeOddEven(head); cout < < "Linked List after " < < "Rearranging:" < < endl; printList(head); return 0; }

Java

// Java program to rearrange nodes // as alternate odd even nodes in // a Singly Linked List import java.util.*; class GFG {// class node static class Node { int data; Node next; }// A utility function to print // linked list static void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.next; } System.out.println(); } // Function to create newNode // in a linkedlist static Node newNode( int key) { Node temp = new Node(); temp.data = https://www.lsbin.com/key; temp.next = null ; return temp; } // Function to insert at beginning static Node insertBeg(Node head, int val) { Node temp = newNode(val); temp.next = head; head = temp; return head; } // Function to rearrange the // odd and even nodes static void rearrangeOddEven(Node head) { 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 odd.push(head); } else if (head.data % 2 == 0 & & i % 2 != 0 ) { // Even Value in Odd Position // Add pointer to current node // in even stack even.push(head); } head = head.next; 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 ); head = insertBeg(head, 7 ); head = insertBeg(head, 6 ); head = insertBeg(head, 5 ); head = insertBeg(head, 3 ); head = insertBeg(head, 2 ); head = insertBeg(head, 1 ); System.out.println("Linked List:" ); printList(head); rearrangeOddEven(head); System.out.println( "Linked List after " + "Rearranging:" ); printList(head); } }// This contributed by Arnab Kundu

python

# Python program to rearrange nodes # as alternate odd even nodes in # a Singly Linked List# Link list node class Node: def __init__( self , data): self .data = https://www.lsbin.com/data self . next = next# A utility function to print # linked list def printList( node):while (node ! = None ) : print (node.data , end =" " ) node = node. nextprint ( "\n" )# Function to create newNode # in a linkedlist def newNode(key):temp = Node( 0 ) temp.data = https://www.lsbin.com/key temp. next = None return temp# Function to insert at beginning def insertBeg(head, val):temp = newNode(val) temp. next = head head = temp return head# Function to rearrange the # odd and even nodes def rearrangeOddEven( head):odd = [] even = [] i = 1while (head ! = None ): if (head.data % 2 ! = 0 and i % 2 = = 0 ): # Odd Value in Even Position # Add pointer to current node # in odd stack odd.append(head)elif (head.data % 2 = = 0 and i % 2 ! = 0 ): # Even Value in Odd Position # Add pointer to current node # in even stack even.append(head)head = head. next i = i + 1while ( 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()return head# Driver codehead = newNode( 8 ) head = insertBeg(head, 7 ) head = insertBeg(head, 6 ) head = insertBeg(head, 5 ) head = insertBeg(head, 3 ) head = insertBeg(head, 2 ) head = insertBeg(head, 1 )print ("Linked List:" ) printList(head) rearrangeOddEven(head)print ( "Linked List after " , "Rearranging:" ) printList(head)# This code is contributed by Arnab Kundu

C#

// C# program to rearrange nodes // as alternate odd even nodes in // a Singly Linked List using System; using System.Collections.Generic; class GFG {// class node public class Node { public int data; public Node next; }// A utility function to print // linked list static void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } Console.WriteLine(); } // Function to create newNode // in a linkedlist static Node newNode( int key) { Node temp = new Node(); temp.data = https://www.lsbin.com/key; temp.next = null ; return temp; } // Function to insert at beginning static Node insertBeg(Node head, int val) { Node temp = newNode(val); temp.next = head; head = temp; return head; } // Function to rearrange the // odd and even nodes static void rearrangeOddEven(Node head) { 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 odd.Push(head); } else if (head.data % 2 == 0 & & i % 2 != 0) { // Even Value in Odd Position // Add pointer to current node // in even stack even.Push(head); } head = head.next; 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) { Node head = newNode(8); head = insertBeg(head, 7); head = insertBeg(head, 6); head = insertBeg(head, 5); head = insertBeg(head, 3); head = insertBeg(head, 2); head = insertBeg(head, 1); Console.WriteLine("Linked List:" ); printList(head); rearrangeOddEven(head); Console.WriteLine( "Linked List after " + "Rearranging:" ); printList(head); } }// This code has been contributed by 29AjayKumar

输出如下：

Linked List: 1 2 3 5 6 7 8 Linked List after Rearranging: 1 2 3 6 5 8 7

时间复杂度：
上)
辅助空间：
上)
方法2(高效)

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 8: Return HEAD. Step 9: End

C ++

// Cpp program to rearrange nodes // as alternate odd even nodes in // a Singly Linked List #include < bits/stdc++.h> using namespace std; // Structure node struct Node { int data; struct Node* next; }; // A utility function to print // linked list void printList( struct Node* node) { while (node != NULL) { cout < < node-> data < < " " ; node = node-> next; } cout < < endl; }// Function to create newNode // in a linkedlist Node* newNode( int key) { Node* temp = new Node; temp-> data = https://www.lsbin.com/key; temp-> next = NULL; return temp; }// Function to insert at beginning Node* insertBeg(Node* head, int val) { Node* temp = newNode(val); temp-> next = head; head = temp; return head; }// Function to rearrange the // odd and even nodes void rearrange(Node** head) { // 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 temp = (*head)-> next; prev_temp = *head; 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; temp-> next = (*head); (*head) = temp; } else { prev_temp = temp; }// Advance Temp Pointer temp = x; }// Step 2 // Split the List into Odd and even temp = (*head)-> next; prev_temp = (*head); 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 i = *head; 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() { Node* head = newNode(8); head = insertBeg(head, 7); head = insertBeg(head, 6); head = insertBeg(head, 3); head = insertBeg(head, 5); head = insertBeg(head, 1); head = insertBeg(head, 2); head = insertBeg(head, 10); cout < <"Linked List:" < < endl; printList(head); cout < < "Rearranged List" < < endl; rearrange(& head); printList(head); }

Java

// Java program to rearrange nodes // as alternate odd even nodes in // a Singly Linked List class GFG {// Structure node static class Node { int data; Node next; }; // A utility function to print // linked list static void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.next; } System.out.println(); } // Function to create newNode // in a linkedlist static Node newNode( int key) { Node temp = new Node(); temp.data = https://www.lsbin.com/key; temp.next = null ; return temp; } // Function to insert at beginning static Node insertBeg(Node head, int val) { Node temp = newNode(val); temp.next = head; head = temp; return head; } // Function to rearrange the // odd and even nodes static Node rearrange(Node head) { // 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 temp = (head).next; prev_temp = head; 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; temp.next = (head); (head) = temp; } else { prev_temp = temp; } // Advance Temp Pointer temp = x; } // Step 2 // Split the List into Odd and even temp = (head).next; prev_temp = (head); 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 i = head; 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 return head; } // Driver Code public static void main(String args[]) { Node head = newNode( 8 ); head = insertBeg(head, 7 ); head = insertBeg(head, 6 ); head = insertBeg(head, 3 ); head = insertBeg(head, 5 ); head = insertBeg(head, 1 ); head = insertBeg(head, 2 ); head = insertBeg(head, 10 ); System.out.println("Linked List:" ); printList(head); System.out.println( "Rearranged List" ); head=rearrange(head); printList(head); } }// This code is contributed by Arnab Kundu

Python3

# Python3 program to rearrange nodes # as alternate odd even nodes in # a Singly Linked List # Structure node class Node :def __init__( self ): self .data = https://www.lsbin.com/0 self . next = None# A utility function to print # linked list def printList(node) : while (node ! = None ) : print (node.data, end =" " ) node = node. nextprint ( " " )# Function to create newNode # in a linkedlist def newNode( key) : temp = Node() temp.data = https://www.lsbin.com/key temp. next = None return temp # Function to insert at beginning def insertBeg( head, val) : temp = newNode(val) temp. next = head head = temp return head # Function to rearrange the # odd and even nodes def rearrange(head) :# 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 temp = (head). next prev_temp = head 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 temp. next = (head) (head) = temp else :prev_temp = temp # Advance Temp Pointer temp = x # Step 2 # Split the List into Odd and even temp = (head). next prev_temp = (head) while (temp ! = None and temp.data % 2 ! = 0 ) : prev_temp = temp temp = temp. nexteven = temp # End the odd List (Make last node None) prev_temp. next = None# Step 3: # Merge Even List into odd i = head 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. nexti. 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 return head# Driver Code head = newNode( 8 ) head = insertBeg(head, 7 ) head = insertBeg(head, 6 ) head = insertBeg(head, 3 ) head = insertBeg(head, 5 ) head = insertBeg(head, 1 ) head = insertBeg(head, 2 ) head = insertBeg(head, 10 ) print ("Linked List:" ) printList(head) print ( "Rearranged List" ) head = rearrange(head) printList(head) # This code is contributed by Arnab Kundu

C#

// C# program to rearrange nodes // as alternate odd even nodes in // a Singly Linked List using System; class GFG { // Structure node public class Node { public int data; public Node next; }; // A utility function to print // linked list static void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } Console.WriteLine(); } // Function to create newNode // in a linkedlist static Node newNode( int key) { Node temp = new Node(); temp.data = https://www.lsbin.com/key; temp.next = null ; return temp; } // Function to insert at beginning static Node insertBeg(Node head, int val) { Node temp = newNode(val); temp.next = head; head = temp; return head; } // Function to rearrange the // odd and even nodes static Node rearrange(Node head) { // 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 temp = (head).next; prev_temp = head; 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; temp.next = (head); (head) = temp; } else { prev_temp = temp; } // Advance Temp Pointer temp = x; } // Step 2 // Split the List into Odd and even temp = (head).next; prev_temp = (head); 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 i = head; 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 return head; } // Driver Code public static void Main(String []args) { Node head = newNode(8); head = insertBeg(head, 7); head = insertBeg(head, 6); head = insertBeg(head, 3); head = insertBeg(head, 5); head = insertBeg(head, 1); head = insertBeg(head, 2); head = insertBeg(head, 10); Console.WriteLine("Linked List:" ); printList(head); Console.WriteLine( "Rearranged List" ); head=rearrange(head); printList(head); } } // 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)

推荐阅读

• 

  八图H5邀请函兴起的原因
• 

  中考志愿怎么填第一批第二批 中考志愿怎么填
• 

  打完新冠疫苗要检查抗体吗
• 

  汽车发动机怠速不稳定是什么原因 发动机怠速不稳定是什么原因有哪些
• 

  笔记本|ROG Zephyrus M16 性能全面升级，兼具台式机级性能
• 

  难忘的父亲节初中作文精选3篇
• 

  酷我音
• 

  广州陶瓷餐具价格怎么样 广州陶瓷餐具哪里有卖
• 

  宜昌一次性吸纳就业补贴对象+电话 宜昌市应届毕业生补贴
• 

  2022世界杯沙特阿拉伯队阵容名单 世界杯沙特阿拉伯队首发阵容
• 

  高三优秀议论文 优秀议论文
• 

  excel如何插入word文档
• 

  志高空调遥控器怎么调制热,注意这些控制技巧
• 

  步步惊心是什么意思 步步惊心的含义
• 

  深圳北站在哪里打的 深圳北站是哪里
• 

  信用卡欠了钱5万实在没钱还会坐牢吗
• 

  真后悔养了博美 养博美犬的好处和坏处
• 

  大学期末考试试卷分析,试卷分析失分原因和改进措施
• 

  住房风水禁忌100例 房屋后面风水禁忌
• 

  美的空调不同产地,每个人都应该了解这些

• JavaScript中的内置字符串是什么（）
• C#标识符用法介绍和代码示例
• C语言中的NULL指针介绍和代码示例
• 算法设计（总和大于给定值的最小子数组）
• win8鼠标双击速度设置小技巧
• win8全屏截图自动保存至桌面的技巧
• win8文件视图一键同步设置技巧
• win8磁盘分区无法重命名的处理技巧
• 拒绝平庸！打造个性化Win8系统MetroQQ图标