给定一个整数链表。任务是编写一个程序来修改链表，使所有偶数出现在修改后的链表中所有奇数之前。不需要保持奇偶节点的顺序与原始列表相同，任务只是重新排列节点，使所有偶数值节点出现在奇数值节点之前。 另见 : 分隔链接列表中的偶数和奇数节点 例子 :
null
输入 ：1->2->3->4->5->6->7->8->9->10->NULL 输出 ：10->8->6->4->2->1->3->5->7->9->NULL 输入 ：4->3->2->1->NULL 输出 ：2->4->3->1->NULL
其思想是根据以下条件，迭代地将链表的所有元素推送到deque：
- 开始遍历链表，如果某个元素是偶数，则将其推到Deque的前面，
- 如果该元素是奇数，则将其推到三角形的后面。
最后，用从第一个元素开始的Deque元素替换链表的所有元素。 以下是上述方法的实施情况：
C++
// CPP program to segregate even and // odd nodes in a linked list using deque #include <bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; /*UTILITY FUNCTIONS*/ /* Push a node to linked list. Note that this function changes the head */ void push( struct Node** head_ref, char 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 */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // printing the linked list void printList( struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf ( "%d " , temp->data); temp = temp->next; } } // Function to rearrange even and odd // elements in a linked list using deque void evenOdd( struct Node* head) { struct Node* temp = head; // Declaring a Deque deque< int > d; // Push all the elements of // linked list in to deque while (temp != NULL) { // if element is even push it // to front of the deque if (temp->data % 2 == 0) d.push_front(temp->data); else // else push at the back of the deque d.push_back(temp->data); temp = temp->next; // increase temp } temp = head; // Replace all elements of the linked list // with the elements of Deque starting from // the first element while (!d.empty()) { temp->data = d.front(); d.pop_front(); temp = temp->next; } } // Driver code int main() { struct Node* head = NULL; push(&head, 10); push(&head, 9); push(&head, 8); push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); cout << "Given linked list: " ; printList(head); evenOdd(head); cout << "After rearrangement: " ; printList(head); return 0; } |
JAVA
// JAVA program to segregate // even and odd nodes in a // linked list using deque import java.util.*; class GFG{ // Link list node static class Node { int data; Node next; }; // UTILITY FUNCTIONS // Push a node to linked list. // Note that this function // changes the head static Node push(Node head_ref, int new_data) { // allocate node Node new_node = new Node(); // put in the data new_node.data = new_data; // link the old list off // the new node new_node.next = head_ref; // move the head to point // to the new node head_ref = new_node; return head_ref; } // Printing the linked list static void printList(Node head) { Node temp = head; while (temp != null ) { System.out.printf( "%d " , temp.data); temp = temp.next; } } // Function to rearrange even // and odd elements in a linked // list using deque static void evenOdd(Node head) { Node temp = head; // Declaring a Deque Deque<Integer> d = new LinkedList<>(); // Push all the elements of // linked list in to deque while (temp != null ) { // if element is even push it // to front of the deque if (temp.data % 2 == 0 ) d.addFirst(temp.data); else // else push at the // back of the deque d.add(temp.data); // increase temp temp = temp.next; } temp = head; // Replace all elements of // the linked list with the // elements of Deque starting // from the first element while (!d.isEmpty()) { temp.data = d.peek(); d.pollFirst(); temp = temp.next; } } // Driver code public static void main(String[] args) { Node head = null ; head = push(head, 10 ); head = push(head, 9 ); head = push(head, 8 ); head = push(head, 7 ); head = push(head, 6 ); head = push(head, 5 ); head = push(head, 4 ); head = push(head, 3 ); head = push(head, 2 ); head = push(head, 1 ); System.out.print( "Given linked list: " ); printList(head); evenOdd(head); System.out.print( "After rearrangement: " ); printList(head); } } // This code is contributed by shikhasingrajput |
python
# Python program to segregate even and # odd nodes in a linked list using deque import collections # Node class class Node: # Function to initialise the node object def __init__( self , data): self .data = data # Assign data self . next = None # UTILITY FUNCTIONS # Push a node to linked list. Note that this function # changes the head def push( head_ref, new_data): # allocate node new_node = Node( 0 ) # put in the data new_node.data = new_data # link the old list off the new node new_node. next = (head_ref) # move the head to point to the new node (head_ref) = new_node return head_ref # printing the linked list def printList( head): temp = head while (temp ! = None ): print ( temp.data, end = " " ) temp = temp. next # Function to rearrange even and odd # elements in a linked list using deque def evenOdd( head): temp = head # Declaring a Deque d = collections.deque([]) # Push all the elements of # linked list in to deque while (temp ! = None ) : # if element is even push it # to front of the deque if (temp.data % 2 = = 0 ): d.appendleft(temp.data) else : # else push at the back of the deque d.append(temp.data) temp = temp. next # increase temp temp = head # Replace all elements of the linked list # with the elements of Deque starting from # the first element while ( len (d) > 0 ) : temp.data = d[ 0 ] d.popleft() temp = temp. next # Driver code head = None head = push(head, 10 ) head = push(head, 9 ) head = push(head, 8 ) head = push(head, 7 ) head = push(head, 6 ) head = push(head, 5 ) head = push(head, 4 ) head = push(head, 3 ) head = push(head, 2 ) head = push(head, 1 ) print ( "Given linked list: " , end = "") printList(head) evenOdd(head) print ( "After rearrangement: " , end = "") printList(head) # This code is contributed by Arnab Kundu |
C#
// C# program to segregate // even and odd nodes in a // linked list using deque using System; using System.Collections.Generic; class GFG{ // Link list node public class Node { public int data; public Node next; }; // UTILITY FUNCTIONS // Push a node to linked list. // Note that this function // changes the head static Node push(Node head_ref, int new_data) { // allocate node Node new_node = new Node(); // put in the data new_node.data = new_data; // link the old list off // the new node new_node.next = head_ref; // move the head to point // to the new node head_ref = new_node; return head_ref; } // Printing the linked list static void printList(Node head) { Node temp = head; while (temp != null ) { Console.Write( " " + temp.data); temp = temp.next; } } // Function to rearrange even // and odd elements in a linked // list using deque static void evenOdd(Node head) { Node temp = head; // Declaring a Deque List< int > d = new List< int >(); // Push all the elements of // linked list in to deque while (temp != null ) { // if element is even push it // to front of the deque if (temp.data % 2 == 0) d.Insert(0, temp.data); else // else push at the // back of the deque d.Add(temp.data); // increase temp temp = temp.next; } temp = head; // Replace all elements of // the linked list with the // elements of Deque starting // from the first element while (d.Count != 0) { temp.data = d[0]; d.RemoveAt(0); temp = temp.next; } } // Driver code public static void Main(String[] args) { Node head = null ; head = push(head, 10); head = push(head, 9); head = push(head, 8); head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); Console.Write( "Given linked list: " ); printList(head); evenOdd(head); Console.Write( "After rearrangement: " ); printList(head); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to segregate // even and odd nodes in a // linked list using deque // Link list node class Node { constructor() { this .data = 0; this .next = null ; } } // UTILITY FUNCTIONS // Push a node to linked list. // Note that this function // changes the head function push(head_ref, new_data) { // allocate node var new_node = new Node(); // put in the data new_node.data = new_data; // link the old list off // the new node new_node.next = head_ref; // move the head to point // to the new node head_ref = new_node; return head_ref; } // Printing the linked list function printList(head) { var temp = head; while (temp != null ) { document.write( " " + temp.data); temp = temp.next; } } // Function to rearrange even // and odd elements in a linked // list using deque function evenOdd(head) { var temp = head; // Declaring a Deque var d = []; // Push all the elements of // linked list in to deque while (temp != null ) { // if element is even push it // to front of the deque if (temp.data % 2 == 0) d.unshift(temp.data); // else push at the // back of the deque else d.push(temp.data); // increase temp temp = temp.next; } temp = head; // Replace all elements of // the linked list with the // elements of Deque starting // from the first element while (d.length != 0) { temp.data = d[0]; d.shift(); temp = temp.next; } } // Driver code var head = null ; head = push(head, 10); head = push(head, 9); head = push(head, 8); head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); document.write( "Given linked list: " ); printList(head); evenOdd(head); document.write( "<br>After rearrangement: " ); printList(head); // This code is contributed by rdtank. </script> |
输出：
Given linked list: 1 2 3 4 5 6 7 8 9 10 After rearrangement: 10 8 6 4 2 1 3 5 7 9
时间复杂性 ：O（N） 辅助空间 ：O（N），其中N是链表中的节点总数。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
