在 Java 中分隔链表的元音和辅音

Question

A linked list can be represented by the following structure:-
struct Node
{
char data;
struct Node* next;
};
struct Node
{
char data;
struct Node* next;
};class Node
{
public char data;
public Node next;
}class Node
{
public char data;
public Node next;
}
You are given a function,
struct Node* ReArrangeVowelsAndConsonants(struct Node* head);struct Node* 

ReArrangeVowelsAndConsonants(struct Node* head);static Node 

ReArrangeVowelsAndConsonants(Node head);static Node 

ReArrangeVowelsAndConsonants(Node head);
The pointer 'head' points to the start of a linked list. Implement the function to rearrange and return the same list so that all the vowels occupy the first half of the list and all the consonants occupy the second half.

Note:

Do not create a new list, modify the existing list.

Relative ordering of vowels and consonants should not change among themselves.

You may assume that the list is of even length and half the nodes contain vowels and the other half contain consonants.

If the list is NULL, then return NULL.

Example:

Input:
a -> k -> r -> i -> t -> e -> o -> m

Output:
a - >i - > e -> o -> k -> r -> t -> m

Explanation:
The consonants k and r in the first half of the list are moved to the second half of the list, while vowels e and o in the second half of the list are moved to first half of the list, keeping the relative ordering same.

我的代码正确执行了操作，但不满足注释中的第 2 点。当我用元音交换辅音时，元素的相对顺序在我的输出中发生了变化。我的代码在下面....我只需要如何使我的代码也适用于这种情况。

import java.io.*;
import java.lang.*;
import java.util.*;
public class Node
{
    public char data;
    public Node next;
    public static Node rearrange(Node head)
    {
        Node start=new Node();
        Node curr=new Node();
        Node temp=new Node();
        start=curr=head;
        int begin=0;
        int flag=0;
        while(head.next!=null)
        { 
            if(head.data=='a'||head.data=='e'||head.data=='i'||head.data=='o'||head.data=='u')
            {      // no change
            }
            else
            {
                curr=head.next;
                do
                {
                     System.out.println("CURR "+curr.data+" HEAD "+head.data);
                    if(curr.data=='a'||curr.data=='e'||curr.data=='i'||curr.data=='o'||curr.data=='u')
                    {
                     temp.data=curr.data;
                     curr.data=head.data;
                     head.data=temp.data;
                     break;
                    }
                }while((curr=curr.next)!=null);
            }
            head=head.next;
        }

        while(start.next!=null)
        {
            System.out.print(start.data+"->");
            start=start.next;
        }
        System.out.print(start.data);
        return start;

    }
    public static void main(String args[])
    {
      Scanner s=new Scanner(System.in);
      int count=0;
      System.out.println("Enter the number of characters:");
      int length=s.nextInt();
      System.out.println("Enter the character seperated by ->");
      String inp=s.next();
      StringTokenizer st=new StringTokenizer(inp,"->");
      Node[] a=new Node[inp.length()];
      for(int i=0;st.hasMoreElements();i++)
      {
        a[i]=new Node();
        a[i].data=(st.nextToken().toString()).charAt(0);
        count++;
      }
      a[count-1].next=null;
      for(int i=0;i<(count-1);i++)
      {
        a[i].next=a[i+1];
      }
      Node start =new Node();
      start=rearrange(a[0]);
    }
}

Answer 1

您可以实现另一种排序算法。如果您不是通过将元音与辅音交换来排序，而是通过将元音与它们的前一个元素（如果它是辅音）一个一个地交换来进行排序并传递元音，您将对列表和元音之间的相对顺序进行排序辅音未受影响。

如果您不确定如何实现这样的排序算法，请查看冒泡排序：

Bubble sort Wikipedia

Answer 2

我认为这个练习使用链表而不是数组是有原因的。如果你被允许 return 一个新的头部，那么你可以使用一种重新排列节点本身的方法，而不是在现有节点之间交换数据。这种方法的好处是只需要遍历一次链表

此实现的想法是保留我们找到的最新元音的标记。如果我们找到另一个元音，我们将它从链中取出并放在现有的最新元音之后。例如：

a -> b -> c -> i -> x -> e

假设我们的 latestVowel 引用引用了 a 节点，并且我们当前到达了 i 节点。我们这样做：

a -> i -> b -> c -> x -> e

所以 a 之后的内容现在是 i 之后的内容，并且 a 直接链接到 i。

要正确删除和添加链接，最好在您正在检查的之前使用项。因此，如果您有 curr，您将检查 curr.next 以查看它是否是元音。如果是，很容易通过将其 next 分配给下一个 curr 来将其从链中删除。当然，你需要先把它添加到新的地方，否则你可能会有一个悬垂的链。

方法如下，每部分都有注释解释：

public static Node rearrangeVowelsAndConsonants(Node head) { Node newHead = head; Node latestVowel; Node curr = head; if (head == null) { return null; } // We need to discover the first vowel in the list. It is going to be // the returned head, and also the initial latestVowel. if (isVowel(head.data)) { // Easy: first element is a vowel. It will also be the new head // and the initial latestVowel; latestVowel = head; } else { // First element is not a vowel. Iterate through the list until we // find a vowel. Note that curr points to the element *before* // the element with the vowel. while (curr.next != null && !isVowel(curr.next.data)) { curr = curr.next; } // This is an edge case where there are only consonants. if (curr.next == null) { return head; } // Set the initial latestVowel and the new head to the vowel // item that we found. Relink the chain of consonants after // that vowel item: // old_head_consonant->consonant1->consonant2->vowel->rest_of_list becomes // vowel->old_head_consonant->consonant1->consonant2->rest_of_list latestVowel = newHead = curr.next; curr.next = curr.next.next; latestVowel.next = head; } // Now traverse the list. Curr is always the item *before* the one we are // checking, so that we can use it to re-link. while ( curr != null && curr.next != null ) { if (isVowel(curr.next.data)) { // The next discovered item is a vowel if (curr == latestVowel) { // If it comes directly after the previous vowel, we don't need // to move items around, just mark the new latestVowel and // advance curr. latestVowel = curr = curr.next; } else { // But if it comes after an intervening chain of consonants, // we need to chain the newly discovered vowel right after // the old vowel. Curr is not changed as after the re-linking // it will have a new next, that has not been checked yet, // and we always keep curr at one before the next to check. Node temp = latestVowel.next; // Keep start of consonant chain latestVowel.next = curr.next; // Chain in new vowel latestVowel = latestVowel.next; // Advance latestVowel curr.next = curr.next.next; // Remove found vowel from previous place latestVowel.next = temp; // Re-link the chain of consonants after lastestVowel. } } else { // No vowel in the next element, advance curr. curr = curr.next; } } return newHead; }

Answer 3

// Here is the Correct Answer  after merging the previous answers. 
// It works Correctly...!
// Splitting Vowels And Consonants 

import java.util.Scanner;
import java.util.StringTokenizer;

public class Node 
{
    public char data;
    public Node next;
    public static Node rearrangeVowelsAndConsonants(Node head) {
        Node newHead = head;
        Node latestVowel;
        Node curr = head;

        if (head == null) {
            return null;
        }


        if (isVowel(head.data)) {

            latestVowel = head;
        } else {

            while (curr.next != null && !isVowel(curr.next.data)) {
                curr = curr.next;
            }

            if (curr.next == null) {
                return head;
            }

            latestVowel = newHead = curr.next;
            curr.next = curr.next.next;
            latestVowel.next = head;
        }


        while ( curr != null && curr.next != null ) {
            if (isVowel(curr.next.data)) {

                if (curr == latestVowel) {

                    latestVowel = curr = curr.next;
                } else {

                    Node temp = latestVowel.next;   
                    latestVowel.next = curr.next;   
                    latestVowel = latestVowel.next; 
                    curr.next = curr.next.next;    
                    latestVowel.next = temp;        
                }
            } else {

                curr = curr.next;
            }
        }
        return newHead;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner s=new Scanner(System.in);
          int count=0;
          System.out.println("Enter the character seperated by ->");
          String inp=s.next();
          StringTokenizer st=new StringTokenizer(inp,"->");
          Node[] a=new Node[inp.length()];
          for(int i=0;st.hasMoreElements();i++)
          {
            a[i]=new Node();
            a[i].data=(st.nextToken().toString()).charAt(0);
            count++;
          }
          a[count-1].next=null;
          for(int i=0;i<(count-1);i++)
          {
            a[i].next=a[i+1];
          }
         Node start=rearrangeVowelsAndConsonants(a[0]);
        while(start.next!=null)
        {
            System.out.print(start.data+"->");
            start=start.next;
        }
        System.out.println(start.data);
        s.close();
    }
    public static boolean isVowel(char ch)
    {
        if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')
        {
            return true;
        }
        else
            return false;

    }

}

在 Java 中分隔链表的元音和辅音

Seperatiing vowels and consonents of Linked List in Java

java

linked-list

list

data-structures