Единственно связанный список в Java

Question

Я только что нашел этот трудный вопрос интервью в Интернете, и я надеялся, что кто-нибудь может помочь мне разобраться в этом.Это общий вопрос ... учитывая односвязный список, поменяйте местами каждый элемент списка попарно, чтобы 1-> 2-> 3-> 4 стал 2-> 1-> 4-> 3.

Вы должны поменять местами элементы, а не значения.Ответ должен работать для круговых списков, где хвост указывает назад на начало списка.Вам не нужно проверять, указывает ли хвост на промежуточный (не головной) элемент.

Итак, я подумал:

public class Node
{
     public int n;     // value
     public Node next; // pointer to next node
}

Каков наилучший способ реализовать это?Кто-нибудь может помочь?

Answer 1

Простое рекурсивное решение в Java:

public static void main(String[] args)
{
    Node n = new Node(1);
    n.next = new Node(2);
    n.next.next = new Node(3);
    n.next.next.next = new Node(4);
    n.next.next.next.next = new Node(5);

    n = swap(n);
}
public static Node swap(Node n)
{
    if(n == null || n.next == null)
        return n;
    Node buffer = n;
    n = n.next;
    buffer.next = n.next;
    n.next = buffer;
    n.next.next = swap(buffer.next);
    return n;
 }

public static class Node
{
    public int data; // value
    public Node next; // pointer to next node

    public Node(int value)
    {
        data = value;
    }
}

Answer 2

Я согласен с @Stephen в том, что я не даю ответ (полностью), но я думаю, что я должен дать вам подсказки.

Важно понимать, что в Java явно не указываются указатели - скорее, когда они не примитивны (например, не char, byte, int, double, float, long , boolean, short) передается функции, она передается как ссылка. Таким образом, вы можете использовать временные переменные для обмена значениями. Попробуйте написать код самостоятельно или посмотрите ниже:

 public static void swapNodeNexts(final Node n1, final Node n2) {  
    final Node n1Next = n1.next;  
    final Node n2Next = n2.next;  
    n2.next = n1Next;  
    n1.next = n2Next;  
 }  

Тогда вам понадобится структура данных для хранения Node s. Важно, чтобы было только четное число Node с (нечетные числа излишне усложняли вещи). Также необходимо инициализировать узлы. Вы должны поместить это в свой основной метод.

  public static final int NUMPAIRS = 3;
 public static void main(final String[] args) {
    final Node[] nodeList = new Node[NUMPAIRS * 2];
    for (int i = 0; i < nodeList.length; i++) {
        nodeList[i] = new Node();
        nodeList[i].n = (i + 1) * 10;
        // 10 20 30 40
    }
    // ...
 } 

Важной частью является установка следующих значений узла. Вы не можете просто пройти цикл с for для всех из них, потому что тогда последний из них next будет выбрасывать IndexOutOfBoundsException. Попробуйте сделать его самостоятельно или загляните в мой.

  for (int i = 0; i < nodeList.length - 1; i++) {
    nodeList[i].next = nodeList[i + 1];
 }
 nodeList[nodeList.length - 1].next = nodeList[0];

Затем запустите на них свою функцию подкачки с помощью цикла for. Но помните, что вы не хотите запускать его на каждом узле ... подумайте немного.

Если вы не можете понять это, вот мой окончательный код:

 // Node
 class Node {
    public int n; // value
    public Node next; // pointer to next node

    @Override
    public String toString() {
        return "Node [n=" + n + ", nextValue=" + next.n + "]";
    }

 }

 // NodeMain
 public class NodeMain {
    public static final int NUMPAIRS = 3;

    public static void main(final String[] args) {
        final Node[] nodeList = new Node[NUMPAIRS * 2];
        for (int i = 0; i < nodeList.length; i++) {
            nodeList[i] = new Node();
            nodeList[i].n = (i + 1) * 10;
            // 10 20 30 40
        }
        for (int i = 0; i < nodeList.length - 1; i++) {
            nodeList[i].next = nodeList[i + 1];
        }
        nodeList[nodeList.length - 1].next = nodeList[0];

        // This makes 1 -> 2 -> 3 -> 4 -> 1 etc.
        printNodes(nodeList);

        for (int i = 0; i < nodeList.length; i += 2) {
            swapNodeNexts(nodeList[i], nodeList[i + 1]);
        }

        // Now: 2 -> 1 -> 4 -> 3 -> 1 etc.
        printNodes(nodeList);

    }

    private static void printNodes(final Node[] nodeList) {
        for (int i = 0; i < nodeList.length; i++) {
            System.out.println("Node " + (i + 1) + ": " + nodeList[i].n
                    + "; next: " + nodeList[i].next.n);
        }
        System.out.println();
    }

    private static void swapNodeNexts(final Node n1, final Node n2) {
        final Node n1Next = n1.next;
        final Node n2Next = n2.next;
        n2.next = n1Next;
        n1.next = n2Next;
    }
 } 

Я надеюсь, что вы смогли понять хотя бы кое-что из этого под руководством. Что еще более важно, однако, важно, чтобы вы поняли концепции здесь. Если у вас есть какие-либо вопросы, просто оставьте комментарий.

Answer 3

Методы, необходимые для запуска этой программы:

public static void main(String[] args) {
    int iNoNodes = 10;
    System.out.println("Total number of nodes : " + iNoNodes);
    Node headNode = NodeUtils.createLinkedListOfNElements(iNoNodes);
    Node ptrToSecondNode = headNode.getNext();
    NodeUtils.printLinkedList(headNode);
    reversePairInLinkedList(headNode);
    NodeUtils.printLinkedList(ptrToSecondNode);
}

Подход почти такой же, другие пытаются объяснить.Код не требует пояснений.

private static void reversePairInLinkedList(Node headNode) {
    Node tempNode = headNode;
    if (tempNode == null || tempNode.getNext() == null)
        return;
    Node a = tempNode;
    Node b = tempNode.getNext();
    Node bNext = b.getNext(); //3
    b.setNext(a);
    if (bNext != null && bNext.getNext() != null)
        a.setNext(bNext.getNext());
    else
        a.setNext(null);
    reversePairInLinkedList(bNext);
}

Answer 4

Алго (узел n1) -

сохранить 2 указателя n1 и n2 на текущих 2 узлах. n1 -> n2 ---> ...

• if (n1 и n2 ссылаются друг на друга) возвращают n2;

• if (n1 равно NULL) вернуть NULL;

• если (n2 равно NULL), вернуть n1;

• if (n1 и n2 не связаны друг с другом и не равны нулю)

• изменить указатель n2 на n1.

• рекурсивно вызвать algorthm для n2.next

• return n2;

Код (рабочий) в c ++

#include <iostream>
using namespace std;

class node
{
public:
int value;
node* next;
node(int val);
};

node::node(int val)
{
value = val;
}

node* reverse(node* n)
{

if(n==NULL) return NULL;
node* nxt = (*n).next;
if(nxt==NULL) return n;

if((*nxt).next==n) return nxt;
else
    {
node* temp = (*nxt).next;
(*nxt).next = n;
 (*n).next   = reverse(temp);
}
return nxt;

}
void print(node* n)
{
node* temp = n;
while(temp!=NULL)
    {
    cout<<(*temp).value;
    temp = (*temp).next;
    }
cout << endl;

}

int main()
{
node* n = new node(0);
node* temp = n;

for(int i=1;i<10;i++)
{

node* n1 = new node(i);
(*temp).next = n1;
temp = n1;
}
print(n);
node* x = reverse(n);
print(x);

}

Answer 5

//2.1 , 2.2 Crack the code interview

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

struct Node{
    int info;
    struct Node *next;
};




 struct Node *insert(struct Node *head,int data){
    struct Node *temp,*ptr;

     temp = (struct Node*)malloc(sizeof(struct Node));
     temp->info=data;
     temp->next=NULL;

     if(head==NULL)
        head=temp;

     else{
        ptr=head;
        while(ptr->next!=NULL)
        {
        ptr=ptr->next;
        }
        ptr->next=temp;
     }
    return head;
 }


 struct Node* reverse(struct Node* head){
    struct Node *current,*prev,*next;
    current = head;
    prev=NULL;
    while(current!=NULL){
        next=current->next;
        current->next = prev;
        prev=current;
        current=next;
    }
    head=prev;
    return head;
}
/*nth till last element in linked list*/

void nthlastElement(struct Node *head,int n){
    struct Node *ptr;
    int last=0,i;
    ptr=head;

    while(ptr!=NULL){
        last++;
        //printf("%d\n",last);
        ptr=ptr->next;
    }

    ptr=head;
    for(i=0;i<n-1;i++){
        ptr=ptr->next;      
    }

    for(i=0;i<=(last-n);i++){
        printf("%d\n",ptr->info);
        ptr=ptr->next;
    }
}

 void display(struct Node* head){
      while(head!=NULL){
        printf("Data:%d\n",head->info);
        head=head->next;
      }
 }



 void deleteDup(struct Node* head){
    struct Node *ptr1,*ptr2,*temp;

    ptr1=head;

    while(ptr1!=NULL&&ptr1->next!=NULL){
            ptr2=ptr1;
          while(ptr2->next!=NULL){
            if(ptr1->info==ptr2->next->info){
                temp=ptr2->next;
                ptr2->next=ptr2->next->next;
                free(temp);
            }
            else{
              ptr2=ptr2->next;
              }

          }  
          ptr1=ptr1->next;
    }
}

 void main(){
    struct Node *head=NULL;
    head=insert(head,10);
    head=insert(head,20);
    head=insert(head,30);
    head=insert(head,10);
    head=insert(head,10);
    printf("BEFORE REVERSE\n"); 
    display(head);
    head=reverse(head);
    printf("AFTER REVERSE\n");
    display(head);
    printf("NTH TO LAST\n");
    nthlastElement(head,2);
     //printf("AFTER DUPLICATE REMOVE\n");
    //deleteDup(head);
    //removeDuplicates(head);
     //display(head);
 }

Answer 6

public static Node swapPairs(Node start)
{
    // empty or one-node lists don't need swapping
    if (start == null || start.next == start) return start;

    // any list we return from here on will start at what's the second node atm
    Node result = start.next;

    Node current = start; 
    Node previous = null;     // so we can fix links from the previous pair

    do
    {
        Node node1 = current;
        Node node2 = current.next;

        // swap node1 and node2 (1->2->? ==> 2->1->?)
        node1.next = node2.next;
        node2.next = node1;

        // If prev exists, it currently points at node1, not node2.  Fix that
        if (previous != null) previous.next = node2;

        previous = current;

        // only have to bump once more to get to the next pair;
        // swapping already bumped us forward once
        current = current.next;

    } while (current != start && current.next != start);

    // The tail needs to point at the new head
    // (if current == start, then previous is the tail, otherwise current is)
    ((current == start) ? previous : current).next = result;

    return result;
}

Answer 7

public static Node swapInPairs(Node n)
{
    Node two;
    if(n ==null ||n.next.next ==null)
    {
        Node one =n;
        Node twoo = n.next;
        twoo.next = one;
        one.next =null;
        return twoo;            
    }
    else{
        Node one = n;
        two = n.next;   
        Node three = two.next;
        two.next =one;
        Node res = swapInPairs(three);
        one.next =res;          
    }
    return two;
}

Я написал код на атомарном уровне. Так что я надеюсь, что это говорит само за себя. Я проверял это. :)

Answer 8

public class Node
{
     public int n;     // value
     public Node next; // pointer to next node
}

Node[] n = new Node[length];

for (int i=0; i<n.length; i++)
{
    Node tmp = n[i];
    n[i] = n[i+1];
    n[i+1] = tmp;
    n[i+1].next = n[i].next; 
    n[i].next = tmp;
}

Answer 9

Да, напишите итерационную подпрограмму, которая выполняет две ссылки в каждой итерации.Запомните ссылку из предыдущей итерации, чтобы вы могли ее исправить, а затем поменять местами две текущие ссылки.Сложные части начинаются (в небольшой степени) и знают, когда нужно закончить (до более крупной), особенно если у вас нечетное количество элементов.

Answer 10

Общий подход заключается в том, чтобы пройти по списку, и на каждом другом шаге вы переупорядочиваете узлы списка, присваивая значения node.

Но я думаю, вы получите больше от этого (т.е. узнать больше) если вы действительно разрабатываете, внедряете и тестируете это самостоятельно.(Вы не получаете бесплатное «позвоните другу» или «спросите ТАК» на собеседовании ...)