重新排列链表，使所有奇数位置节点在一起，所有偶数位置节点在一起， 例如：
null
Input: 1->2->3->4Output: 1->3->2->4Input: 10->22->30->43->56->70Output: 10->30->56->22->43->70
这个问题的重要一点是确保以下所有案件都得到处理 1） 空链表 2） 只有一个节点的链表 3） 只有两个节点的链表 4） 节点数为奇数的链表 5） 节点数为偶数的链表 下面的程序分别在奇数和偶数位置为当前节点维护两个指针“奇数”和“偶数”。我们还存储偶数链表的第一个节点，以便在将所有奇数和偶数节点连接在两个不同的列表中后，将偶数链表附加到奇数链表的末尾。
C++
// C++ program to rearrange a linked list in such a // way that all odd positioned node are stored before // all even positioned nodes #include<bits/stdc++.h> using namespace std; // Linked List Node class Node { public : int data; Node* next; }; // A utility function to create a new node Node* newNode( int key) { Node *temp = new Node; temp->data = key; temp->next = NULL; return temp; } // Rearranges given linked list such that all even // positioned nodes are before odd positioned. // Returns new head of linked List. Node *rearrangeEvenOdd(Node *head) { // Corner case if (head == NULL) return NULL; // Initialize first nodes of even and // odd lists Node *odd = head; Node *even = head->next; // Remember the first node of even list so // that we can connect the even list at the // end of odd list. Node *evenFirst = even; while (1) { // If there are no more nodes, then connect // first node of even list to the last node // of odd list if (!odd || !even || !(even->next)) { odd->next = evenFirst; break ; } // Connecting odd nodes odd->next = even->next; odd = even->next; // If there are NO more even nodes after // current odd. if (odd->next == NULL) { even->next = NULL; odd->next = evenFirst; break ; } // Connecting even nodes even->next = odd->next; even = odd->next; } return head; } // A utility function to print a linked list void printlist(Node * node) { while (node != NULL) { cout << node->data << "->" ; node = node->next; } cout << "NULL" << endl; } // Driver code int main( void ) { Node *head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); head->next->next->next->next = newNode(5); cout << "Given Linked List" ; printlist(head); head = rearrangeEvenOdd(head); cout << "Modified Linked List" ; printlist(head); return 0; } // This is code is contributed by rathbhupendra |
C
// C program to rearrange a linked list in such a // way that all odd positioned node are stored before // all even positioned nodes #include<bits/stdc++.h> using namespace std; // Linked List Node struct Node { int data; struct Node* next; }; // A utility function to create a new node Node* newNode( int key) { Node *temp = new Node; temp->data = key; temp->next = NULL; return temp; } // Rearranges given linked list such that all even // positioned nodes are before odd positioned. // Returns new head of linked List. Node *rearrangeEvenOdd(Node *head) { // Corner case if (head == NULL) return NULL; // Initialize first nodes of even and // odd lists Node *odd = head; Node *even = head->next; // Remember the first node of even list so // that we can connect the even list at the // end of odd list. Node *evenFirst = even; while (1) { // If there are no more nodes, then connect // first node of even list to the last node // of odd list if (!odd || !even || !(even->next)) { odd->next = evenFirst; break ; } // Connecting odd nodes odd->next = even->next; odd = even->next; // If there are NO more even nodes after // current odd. if (odd->next == NULL) { even->next = NULL; odd->next = evenFirst; break ; } // Connecting even nodes even->next = odd->next; even = odd->next; } return head; } // A utility function to print a linked list void printlist(Node * node) { while (node != NULL) { cout << node->data << "->" ; node = node->next; } cout << "NULL" << endl; } // Driver code int main( void ) { Node *head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); head->next->next->next->next = newNode(5); cout << "Given Linked List" ; printlist(head); head = rearrangeEvenOdd(head); cout << "Modified Linked List" ; printlist(head); return 0; } |
JAVA
// Java program to rearrange a linked list // in such a way that all odd positioned // node are stored before all even positioned nodes class GfG { // Linked List Node static class Node { int data; Node next; } // A utility function to create a new node static Node newNode( int key) { Node temp = new Node(); temp.data = key; temp.next = null ; return temp; } // Rearranges given linked list // such that all even positioned // nodes are before odd positioned. // Returns new head of linked List. static Node rearrangeEvenOdd(Node head) { // Corner case if (head == null ) return null ; // Initialize first nodes of even and // odd lists Node odd = head; Node even = head.next; // Remember the first node of even list so // that we can connect the even list at the // end of odd list. Node evenFirst = even; while ( 1 == 1 ) { // If there are no more nodes, // then connect first node of even // list to the last node of odd list if (odd == null || even == null || (even.next) == null ) { odd.next = evenFirst; break ; } // Connecting odd nodes odd.next = even.next; odd = even.next; // If there are NO more even nodes // after current odd. if (odd.next == null ) { even.next = null ; odd.next = evenFirst; break ; } // Connecting even nodes even.next = odd.next; even = odd.next; } return head; } // A utility function to print a linked list static void printlist(Node node) { while (node != null ) { System.out.print(node.data + "->" ); node = node.next; } System.out.println( "NULL" ) ; } // Driver code public static void main(String[] args) { Node head = newNode( 1 ); head.next = newNode( 2 ); head.next.next = newNode( 3 ); head.next.next.next = newNode( 4 ); head.next.next.next.next = newNode( 5 ); System.out.println( "Given Linked List" ); printlist(head); head = rearrangeEvenOdd(head); System.out.println( "Modified Linked List" ); printlist(head); } } // This code is contributed by Prerna saini |
Python3
# Python3 program to rearrange a linked list # in such a way that all odd positioned # node are stored before all even positioned nodes # Linked List Node class Node: def __init__( self , d): self .data = d self . next = None class LinkedList: def __init__( self ): self .head = None # A utility function to create # a new node def newNode( self , key): temp = Node(key) self . next = None return temp # Rearranges given linked list # such that all even positioned # nodes are before odd positioned. # Returns new head of linked List. def rearrangeEvenOdd( self , head): # Corner case if ( self .head = = None ): return None # Initialize first nodes of # even and odd lists odd = self .head even = self .head. next # Remember the first node of even list so # that we can connect the even list at the # end of odd list. evenFirst = even while ( 1 = = 1 ): # If there are no more nodes, # then connect first node of even # list to the last node of odd list if (odd = = None or even = = None or (even. next ) = = None ): odd. next = evenFirst break # Connecting odd nodes odd. next = even. next odd = even. next # If there are NO more even nodes # after current odd. if (odd. next = = None ): even. next = None odd. next = evenFirst break # Connecting even nodes even. next = odd. next even = odd. next return head # A utility function to print a linked list def printlist( self , node): while (node ! = None ): print (node.data, end = "") print ( "->" , end = "") node = node. next print ( "NULL" ) # Function to insert a new node # at the beginning def push( self , new_data): new_node = Node(new_data) new_node. next = self .head self .head = new_node # Driver code ll = LinkedList() ll.push( 5 ) ll.push( 4 ) ll.push( 3 ) ll.push( 2 ) ll.push( 1 ) print ( "Given Linked List" ) ll.printlist(ll.head) start = ll.rearrangeEvenOdd(ll.head) print ( "Modified Linked List" ) ll.printlist(start) # This code is contributed by Prerna Saini |
C#
// C# program to rearrange a linked list // in such a way that all odd positioned // node are stored before all even positioned nodes using System; class GfG { // Linked List Node class Node { public int data; public Node next; } // A utility function to create a new node static Node newNode( int key) { Node temp = new Node(); temp.data = key; temp.next = null ; return temp; } // Rearranges given linked list // such that all even positioned // nodes are before odd positioned. // Returns new head of linked List. static Node rearrangeEvenOdd(Node head) { // Corner case if (head == null ) return null ; // Initialize first nodes of even and // odd lists Node odd = head; Node even = head.next; // Remember the first node of even list so // that we can connect the even list at the // end of odd list. Node evenFirst = even; while (1 == 1) { // If there are no more nodes, // then connect first node of even // list to the last node of odd list if (odd == null || even == null || (even.next) == null ) { odd.next = evenFirst; break ; } // Connecting odd nodes odd.next = even.next; odd = even.next; // If there are NO more even nodes // after current odd. if (odd.next == null ) { even.next = null ; odd.next = evenFirst; break ; } // Connecting even nodes even.next = odd.next; even = odd.next; } return head; } // A utility function to print a linked list static void printlist(Node node) { while (node != null ) { Console.Write(node.data + "->" ); node = node.next; } Console.WriteLine( "NULL" ) ; } // Driver code public static void Main() { Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); head.next.next.next.next = newNode(5); Console.WriteLine( "Given Linked List" ); printlist(head); head = rearrangeEvenOdd(head); Console.WriteLine( "Modified Linked List" ); printlist(head); } } /* This code is contributed PrinciRaj1992 */ |
Javascript
<script> // Javascript program to rearrange a linked list // in such a way that all odd positioned // node are stored before all even positioned nodes // Linked List Node class Node { constructor() { this .data = 0; this .next = null ; } } // A utility function to create a new node function newNode(key) { var temp = new Node(); temp.data = key; temp.next = null ; return temp; } // Rearranges given linked list // such that all even positioned // nodes are before odd positioned. // Returns new head of linked List. function rearrangeEvenOdd(head) { // Corner case if (head == null ) return null ; // Initialize first nodes of even and // odd lists var odd = head; var even = head.next; // Remember the first node of even list so // that we can connect the even list at the // end of odd list. var evenFirst = even; while (1 == 1) { // If there are no more nodes, // then connect first node of even // list to the last node of odd list if (odd == null || even == null || (even.next) == null ) { odd.next = evenFirst; break ; } // Connecting odd nodes odd.next = even.next; odd = even.next; // If there are NO more even nodes // after current odd. if (odd.next == null ) { even.next = null ; odd.next = evenFirst; break ; } // Connecting even nodes even.next = odd.next; even = odd.next; } return head; } // A utility function to print a linked list function printlist(node) { while (node != null ) { document.write(node.data + "->" ); node = node.next; } document.write( "NULL<br/>" ); } // Driver code var head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); head.next.next.next.next = newNode(5); document.write( "Given Linked List<br/>" ); printlist(head); head = rearrangeEvenOdd(head); document.write( "Modified Linked List<br/>" ); printlist(head); // This code contributed by gauravrajput1 </script> |
输出：
Given Linked List1->2->3->4->5->NULLModified Linked List1->3->5->2->4->NULL
本文由 苛刻的贱民 .请看 这里是另一个代码 贡献者 乔塔姆·辛格 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
