Danh sách liên kết đơn lẻ trong java

Question

Tôi vừa tìm thấy câu hỏi phỏng vấn khó trực tuyến này và tôi hy vọng một người nào đó có thể giúp tôi hiểu về nó. Đó là một câu hỏi chung ... đưa ra một danh sách liên kết đơn lẻ, hoán đổi từng phần tử của danh sách theo cặp sao cho 1 -> 2-> 3-> 4 sẽ trở thành 2> 1-> 4 -> 3.

Bạn phải trao đổi các phần tử, chứ không phải các giá trị. Câu trả lời sẽ làm việc cho các danh sách vòng tròn nơi đuôi trỏ trở lại phần đầu của danh sách. Bạn không cần phải kiểm tra xem đuôi có trỏ đến phần tử trung gian (không phải đầu) hay không.

Vì vậy, tôi nghĩ:

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

cách tốt nhất để thực hiện điều này là gì? Có ai giúp được không?

Answer 1

Tôi đồng ý với @Khi không đưa ra câu trả lời (hoàn toàn), nhưng tôi nghĩ tôi nên cung cấp cho bạn gợi ý.

Một điều quan trọng cần hiểu là Java không xác định rõ ràng con trỏ - đúng hơn, bất cứ khi nào một tổ chức phi nguyên thủy (ví dụ như không char, byte, int, double, float, long, boolean, short) được chuyển đến một chức năng, nó được chuyển như một tham chiếu. Vì vậy, bạn có thể sử dụng các biến tạm thời để hoán đổi các giá trị. Hãy thử tự viết mã cho chính bạn hoặc xem bên dưới:

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; 
} 

Sau đó, bạn sẽ cần cấu trúc dữ liệu để giữ Node s. Điều quan trọng là chỉ có một số chẵn Node s (số lẻ không cần thiết phức tạp). Nó cũng cần thiết để khởi tạo các nút. Bạn nên đặt điều này trong phương pháp chính của bạn.

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 
    } 
    // ... 
} 

Phần quan trọng là đặt giá trị tiếp theo cho nút. Bạn không thể lặp qua vòng lặp for cho tất cả chúng, bởi vì sau đó vòng cuối cùng của next sẽ ném một số IndexOutOfBoundsException. Cố gắng tự mình làm một, hoặc nhìn trộm tôi.

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

Sau đó chạy chức năng hoán đổi trên chúng với vòng lặp for. Nhưng hãy nhớ, bạn không muốn chạy nó trên mỗi nút… suy nghĩ về nó một chút.

Nếu bạn không thể tìm ra nó, đây là mã cuối cùng của tôi:

// 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; 
    } 
} 

Tôi hy vọng bạn đã có thể tìm ra ít nhất một số này theo hướng dẫn. Quan trọng hơn, tuy nhiên, điều quan trọng là bạn hiểu các khái niệm ở đây. Nếu bạn có bất kỳ câu hỏi nào, chỉ cần để lại nhận xét.

Answer 2

Cách tiếp cận chung để thực hiện là bước qua danh sách và trên mọi bước khác, bạn sắp xếp lại các nút danh sách bằng cách gán giá trị node.

Nhưng tôi nghĩ bạn sẽ nhận được nhiều hơn từ điều này (ví dụ: tìm hiểu thêm) nếu bạn thực sự thiết kế, triển khai và tự mình kiểm tra. (Bạn không nhận được "điện thoại miễn phí của bạn bè" hoặc "yêu cầu SO" tại cuộc phỏng vấn xin việc ...)

Answer 3

Yep, viết thường trình lặp lại tiến hành hai liên kết trong mỗi lần lặp. Hãy nhớ liên kết từ lần lặp trước để bạn có thể vá lại, sau đó hoán đổi hai liên kết hiện tại. Các phần phức tạp đang bắt đầu (ở một mức độ nhỏ) và biết khi nào kết thúc (đến một phần lớn hơn), đặc biệt nếu bạn kết thúc có một số lẻ các phần tử.

Answer 4

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 5

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; 
} 

Tôi đã viết mã ở cấp nguyên tử. Vì vậy, tôi hy vọng nó là tự giải thích. Tôi đã thử nghiệm nó. :)

Answer 6

Algo (nút n1) -

giữ 2 con trỏ n1 và n2, tại 2 nút hiện hành. n1 -> n2 ---> ...

• nếu (n1 và n2 liên kết với nhau) trả lại n2;

• nếu (n1 là NULL) trả về NULL;

• nếu (n2 là NULL) trả lại n1;

• if (n1 và n2 không liên kết với nhau và không phải null)

• thay đổi con trỏ của n2 n1.

• gọi các algorthm đệ quy trên n2.next n2

• trở lại;

Mã (làm việc) trong 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 7

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 8

giải pháp đệ quy đơn giản trong 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 9

phương pháp cần thiết để chạy chương trình này:

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); 
} 

Cách tiếp cận gần như giống nhau, những người khác đang cố giải thích. Mã là tự giải thích.

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 10

//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); 
}