给定一个链表和一个值x，对其进行分区，使小于x的所有节点先出现，然后是值等于x的所有节点，最后是值大于或等于x的节点。应保留三个分区中每个节点的原始相对顺序。隔板必须在适当的位置工作。 例如：
null
Input : 1->4->3->2->5->2->3, x = 3Output: 1->2->2->3->3->4->5Input : 1->4->2->10 x = 3Output: 1->2->4->10Input : 10->4->20->10->3 x = 3Output: 3->10->4->20->10
为了解决这个问题，我们可以使用 分割法 属于 快速排序 但这不会保留两个分区中每个节点的原始相对顺序。 下面是解决这个问题的算法：
- 将下面三个链表的第一个和最后一个节点初始化为空。
- 小于x的值的链接列表。
- 等于x的值的链接列表。
- 大于x的值的链接列表。
- 现在遍历原始的链表。如果节点的值小于x，则将其附加到较小列表的末尾。如果该值等于x，则在“相等”列表的末尾。如果某个值更大，则位于较大列表的末尾。
- 现在连接三个列表。
下面是上述想法的实施。
C++
// C++ program to partition a linked list around a // given value. #include<bits/stdc++.h> using namespace std; /* Link list Node */ struct Node { int data; struct Node* next; }; // A utility function to create a new node Node *newNode( int data) { struct Node* new_node = new Node; new_node->data = data; new_node->next = NULL; return new_node; } // Function to make two separate lists and return // head after concatenating struct Node *partition( struct Node *head, int x) { /* Let us initialize first and last nodes of three linked lists 1) Linked list of values smaller than x. 2) Linked list of values equal to x. 3) Linked list of values greater than x.*/ struct Node *smallerHead = NULL, *smallerLast = NULL; struct Node *greaterLast = NULL, *greaterHead = NULL; struct Node *equalHead = NULL, *equalLast = NULL; // Now iterate original list and connect nodes // of appropriate linked lists. while (head != NULL) { // If current node is equal to x, append it // to the list of x values if (head->data == x) { if (equalHead == NULL) equalHead = equalLast = head; else { equalLast->next = head; equalLast = equalLast->next; } } // If current node is less than X, append // it to the list of smaller values else if (head->data < x) { if (smallerHead == NULL) smallerLast = smallerHead = head; else { smallerLast->next = head; smallerLast = head; } } else // Append to the list of greater values { if (greaterHead == NULL) greaterLast = greaterHead = head; else { greaterLast->next = head; greaterLast = head; } } head = head->next; } // Fix end of greater linked list to NULL if this // list has some nodes if (greaterLast != NULL) greaterLast->next = NULL; // Connect three lists // If smaller list is empty if (smallerHead == NULL) { if (equalHead == NULL) return greaterHead; equalLast->next = greaterHead; return equalHead; } // If smaller list is not empty // and equal list is empty if (equalHead == NULL) { smallerLast->next = greaterHead; return smallerHead; } // If both smaller and equal list // are non-empty smallerLast->next = equalHead; equalLast->next = greaterHead; return smallerHead; } /* Function to print linked list */ void printList( struct Node *head) { struct Node *temp = head; while (temp != NULL) { printf ( "%d " , temp->data); temp = temp->next; } } // Driver program to run the case int main() { /* Start with the empty list */ struct Node* head = newNode(10); head->next = newNode(4); head->next->next = newNode(5); head->next->next->next = newNode(30); head->next->next->next->next = newNode(2); head->next->next->next->next->next = newNode(50); int x = 3; head = partition(head, x); printList(head); return 0; } |
JAVA
// Java program to partition a // linked list around a given value. class GfG { /* Link list Node */ static class Node { int data; Node next; } // A utility function to create a new node static Node newNode( int data) { Node new_node = new Node(); new_node.data = data; new_node.next = null ; return new_node; } // Function to make two separate lists and return // head after concatenating static Node partition(Node head, int x) { /* Let us initialize first and last nodes of three linked lists 1) Linked list of values smaller than x. 2) Linked list of values equal to x. 3) Linked list of values greater than x.*/ Node smallerHead = null , smallerLast = null ; Node greaterLast = null , greaterHead = null ; Node equalHead = null , equalLast = null ; // Now iterate original list and connect nodes // of appropriate linked lists. while (head != null ) { // If current node is equal to x, append it // to the list of x values if (head.data == x) { if (equalHead == null ) equalHead = equalLast = head; else { equalLast.next = head; equalLast = equalLast.next; } } // If current node is less than X, append // it to the list of smaller values else if (head.data < x) { if (smallerHead == null ) smallerLast = smallerHead = head; else { smallerLast.next = head; smallerLast = head; } } else // Append to the list of greater values { if (greaterHead == null ) greaterLast = greaterHead = head; else { greaterLast.next = head; greaterLast = head; } } head = head.next; } // Fix end of greater linked list to NULL if this // list has some nodes if (greaterLast != null ) greaterLast.next = null ; // Connect three lists // If smaller list is empty if (smallerHead == null ) { if (equalHead == null ) return greaterHead; equalLast.next = greaterHead; return equalHead; } // If smaller list is not empty // and equal list is empty if (equalHead == null ) { smallerLast.next = greaterHead; return smallerHead; } // If both smaller and equal list // are non-empty smallerLast.next = equalHead; equalLast.next = greaterHead; return smallerHead; } /* Function to print linked list */ static void printList(Node head) { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } } // Driver code public static void main(String[] args) { /* Start with the empty list */ Node head = newNode( 10 ); head.next = newNode( 4 ); head.next.next = newNode( 5 ); head.next.next.next = newNode( 30 ); head.next.next.next.next = newNode( 2 ); head.next.next.next.next.next = newNode( 50 ); int x = 3 ; head = partition(head, x); printList(head); } } // This code is contributed by Prerna saini. |
Python3
# Python3 program to partition a # linked list around a given value. # Link list Node class Node: def __init__( self ): self .data = 0 self . next = None # A utility function to create a new node def newNode( data): new_node = Node() new_node.data = data new_node. next = None return new_node # Function to make two separate lists and return # head after concatenating def partition( head, x) : # Let us initialize first and last nodes of # three linked lists # 1) Linked list of values smaller than x. # 2) Linked list of values equal to x. # 3) Linked list of values greater than x. smallerHead = None smallerLast = None greaterLast = None greaterHead = None equalHead = None equalLast = None # Now iterate original list and connect nodes # of appropriate linked lists. while (head ! = None ) : # If current node is equal to x, append it # to the list of x values if (head.data = = x): if (equalHead = = None ): equalHead = equalLast = head else : equalLast. next = head equalLast = equalLast. next # If current node is less than X, append # it to the list of smaller values elif (head.data < x): if (smallerHead = = None ): smallerLast = smallerHead = head else : smallerLast. next = head smallerLast = head else : # Append to the list of greater values if (greaterHead = = None ) : greaterLast = greaterHead = head else : greaterLast. next = head greaterLast = head head = head. next # Fix end of greater linked list to None if this # list has some nodes if (greaterLast ! = None ) : greaterLast. next = None # Connect three lists # If smaller list is empty if (smallerHead = = None ) : if (equalHead = = None ) : return greaterHead equalLast. next = greaterHead return equalHead # If smaller list is not empty # and equal list is empty if (equalHead = = None ) : smallerLast. next = greaterHead return smallerHead # If both smaller and equal list # are non-empty smallerLast. next = equalHead equalLast. next = greaterHead return smallerHead # Function to print linked list def printList(head) : temp = head while (temp ! = None ): print (temp.data ,end = " " ) temp = temp. next # Driver code # Start with the empty list head = newNode( 10 ) head. next = newNode( 4 ) head. next . next = newNode( 5 ) head. next . next . next = newNode( 30 ) head. next . next . next . next = newNode( 2 ) head. next . next . next . next . next = newNode( 50 ) x = 3 head = partition(head, x) printList(head) # This code is contributed by Arnab Kundu. |
C#
// C# program to partition a // linked list around a given value. using System; public class GfG { /* Link list Node */ public class Node { public int data; public Node next; } // A utility function to create a new node static Node newNode( int data) { Node new_node = new Node(); new_node.data = data; new_node.next = null ; return new_node; } // Function to make two separate lists and return // head after concatenating static Node partition(Node head, int x) { /* Let us initialize first and last nodes of three linked lists 1) Linked list of values smaller than x. 2) Linked list of values equal to x. 3) Linked list of values greater than x.*/ Node smallerHead = null , smallerLast = null ; Node greaterLast = null , greaterHead = null ; Node equalHead = null , equalLast = null ; // Now iterate original list and connect nodes // of appropriate linked lists. while (head != null ) { // If current node is equal to x, append it // to the list of x values if (head.data == x) { if (equalHead == null ) equalHead = equalLast = head; else { equalLast.next = head; equalLast = equalLast.next; } } // If current node is less than X, append // it to the list of smaller values else if (head.data < x) { if (smallerHead == null ) smallerLast = smallerHead = head; else { smallerLast.next = head; smallerLast = head; } } else // Append to the list of greater values { if (greaterHead == null ) greaterLast = greaterHead = head; else { greaterLast.next = head; greaterLast = head; } } head = head.next; } // Fix end of greater linked list to NULL if this // list has some nodes if (greaterLast != null ) greaterLast.next = null ; // Connect three lists // If smaller list is empty if (smallerHead == null ) { if (equalHead == null ) return greaterHead; equalLast.next = greaterHead; return equalHead; } // If smaller list is not empty // and equal list is empty if (equalHead == null ) { smallerLast.next = greaterHead; return smallerHead; } // If both smaller and equal list // are non-empty smallerLast.next = equalHead; equalLast.next = greaterHead; return smallerHead; } /* Function to print linked list */ static void printList(Node head) { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } } // Driver code public static void Main() { /* Start with the empty list */ Node head = newNode(10); head.next = newNode(4); head.next.next = newNode(5); head.next.next.next = newNode(30); head.next.next.next.next = newNode(2); head.next.next.next.next.next = newNode(50); int x = 3; head = partition(head, x); printList(head); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript program to partition a // linked list around a given value. /* Link list Node */ class Node { constructor() { this .data = 0; this .next = null ; } } // A utility function to create a new node function newNode(data) { var new_node = new Node(); new_node.data = data; new_node.next = null ; return new_node; } // Function to make two separate lists and return // head after concatenating function partition(head , x) { /* Let us initialize first and last nodes of three linked lists 1) Linked list of values smaller than x. 2) Linked list of values equal to x. 3) Linked list of values greater than x. */ var smallerHead = null , smallerLast = null ; var greaterLast = null , greaterHead = null ; var equalHead = null , equalLast = null ; // Now iterate original list and connect nodes // of appropriate linked lists. while (head != null ) { // If current node is equal to x, append it // to the list of x values if (head.data == x) { if (equalHead == null ) equalHead = equalLast = head; else { equalLast.next = head; equalLast = equalLast.next; } } // If current node is less than X, append // it to the list of smaller values else if (head.data < x) { if (smallerHead == null ) smallerLast = smallerHead = head; else { smallerLast.next = head; smallerLast = head; } } else // Append to the list of greater values { if (greaterHead == null ) greaterLast = greaterHead = head; else { greaterLast.next = head; greaterLast = head; } } head = head.next; } // Fix end of greater linked list to NULL if this // list has some nodes if (greaterLast != null ) greaterLast.next = null ; // Connect three lists // If smaller list is empty if (smallerHead == null ) { if (equalHead == null ) return greaterHead; equalLast.next = greaterHead; return equalHead; } // If smaller list is not empty // and equal list is empty if (equalHead == null ) { smallerLast.next = greaterHead; return smallerHead; } // If both smaller and equal list // are non-empty smallerLast.next = equalHead; equalLast.next = greaterHead; return smallerHead; } /* Function to print linked list */ function printList(head) { var temp = head; while (temp != null ) { document.write(temp.data + " " ); temp = temp.next; } } // Driver code /* Start with the empty list */ var head = newNode(10); head.next = newNode(4); head.next.next = newNode(5); head.next.next.next = newNode(30); head.next.next.next.next = newNode(2); head.next.next.next.next.next = newNode(50); var x = 3; head = partition(head, x); printList(head); // This code contributed by aashish1995 </script> |
输出：
2 10 4 5 30 50
本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
