Xếp mỗi k các nút của một danh sách liên kết

Question

tôi đang chuẩn bị cho một cuộc phỏng vấn kỹ thuật và tôi đang bị mắc kẹt tại văn bản chương trình này để đảo ngược tất cả các k nút của danh sách liên kết.

Ví dụ

1->2->3->4->5->6 //Linked List 
2->1->4->3->6->5 //Output for k=2 

EDIT:

Đây là mã của tôi. Tôi chỉ nhận được 6-> 5 là đầu ra.

struct node* recrev(struct node* noode,int c) 
{ 
struct node* root=noode,*temp,*final,*prev=NULL; 
int count=0; 
while(root!=NULL && count<c) 
{ 
    count++; 
    temp=root->link; 
    root->link=prev; 
    prev=root; 
    root=temp; 
} 
if(temp!=NULL) 
    noode->link=recrev(temp,c); 
else 
    return prev; 

} 

Mọi trợ giúp đều được đánh giá cao. Cảm ơn.

EDIT: Tôi cố gắng thực hiện Eran Zimmerman Thuật toán như dưới đây.

struct node* rev(struct node* root,int c) 
{ 
struct node* first=root,*prev,*remaining=NULL; 
int count=0; 
while(first!=NULL && count<c) 
{ 

    count++; 
    prev=first->link; 
    first->link=remaining; 
    remaining=first; 
    first=prev; 
} 
return remaining; 
} 
struct node* recc(struct node* root,int c) 
{ 
struct node* final,*temp,*n=root,*t; 
int count=0; 
while(n!=NULL) 
{ 
     count=0; 
     temp=rev(n,c); 
     final=temp; 


    while(n!=NULL && count<c) 
    { 
    printf("inside while: %c\n",n->data); // This gets printed only once 
    if(n->link==NULL) printf("NULL"); //During first iteration itself NULL gets printed 
     n=n->link; 
     final=final->link; 
     count++; 
    } 

} 
final->link=NULL; 
return final; 
} 

Answer 1

Tôi thích bạn đệ quy, mặc dù nó có thể không phải là giải pháp tốt nhất. Tôi có thể nhìn thấy từ mã của bạn mà bạn nghĩ rằng nó sâu khi bạn thiết kế nó. Bạn chỉ là một bước đi từ câu trả lời.

Nguyên nhân: Bạn quên trả lại nút root mới trong trường hợp đệ quy của bạn.

if(temp!=NULL) 
    noode->link=recrev(temp,c); 
    // You need return the new root node here 
    // which in this case is prev: 
    // return prev; 
else 
    return prev; 

Answer 2

tôi sẽ làm một cái gì đó như thế này:

init curr (node pointer) to point to the beginning of the list. 
while end of list is not reached (by curr): 
- reverse(curr, k) 
- advance curr k times 

và đảo ngược là một hàm đảo ngược các yếu tố k đầu tiên bắt đầu từ Curr.

điều này có thể không phải là thanh lịch nhất hoặc việc thực hiện hiệu quả nhất, nhưng nó hoạt động và khá đơn giản.

để trả lời liên quan đến mã bạn nói thêm:

bạn quay trở lại trước, mà là liên tục được nâng cao. bạn nên trả lại phần đầu của danh sách.

Answer 3

(tôi giả sử đây là một danh sách đơn lẻ liên kết.) Bạn có thể giữ một con trỏ tạm thời (cho phép gọi nó là nodek) và trước nó k lần trong một vòng lặp while. Điều này sẽ có O (k). Bây giờ bạn có một con trỏ để bắt đầu danh sách và đến phần tử cuối cùng của danh sách con. Để đảo ngược ở đây, bạn loại bỏ từ đầu là O (1) và thêm vào nodek là O (1). Làm điều này cho tất cả các yếu tố, vì vậy đây là O (k) một lần nữa. Bây giờ cập nhật root thành nodek, và chạy vòng lặp while trên nodek một lần nữa (để có được vị trí mới của nodek) và lặp lại toàn bộ quá trình này một lần nữa. Hãy nhớ làm bất kỳ kiểm tra lỗi nào trên đường đi. Giải pháp này sẽ chạy ở O (n) chỉ với không gian O (1).

Answer 4

Đây là mã giả.

temp = main_head = node.alloc(); 
while (!linked_list.is_empty()) 
{ 
    push k nodes on stack 
    head = stack.pop(); 
    temp->next = head; 
    temp = head; 
    while (!stack.empty()) 
    { 
     temp->next = stack.pop(); 
     temp = temp->next; 
    } 
} 

Tôi đã triển khai bản demo mã này. Tha thứ cho việc thực hiện lộn xộn. Điều này sẽ hoạt động với bất kỳ giá trị nào của k. Mỗi đoạn có kích thước k được đảo ngược riêng biệt trong vòng lặp bên trong và các đoạn khác nhau được liên kết với nhau trong vòng ngoài trước khi nhập vào bên trong. temp theo dõi nút cuối cùng của danh sách phụ có kích thước k và head giữ giá trị tiếp theo của danh sách phụ tiếp theo và chúng tôi liên kết chúng. Một ngăn xếp rõ ràng được sử dụng để thực hiện việc đảo ngược.

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

typedef struct _node { 
    int a; 
    struct _node *next; 
} node_t; 

typedef struct _stack { 
    node_t *arr[128]; 
    int top; 
} stack_t; 

void stk_init (stack_t *stk) 
{ 
    stk->top = -1; 
} 

void push (stack_t *stk, node_t *val) 
{ 
    stk->arr[++(stk->top)] = val; 
} 

node_t *pop (stack_t *stk) 
{ 
    if (stk->top == -1) 
    return NULL; 
    return stk->arr[(stk->top)--]; 
} 

int empty (stack_t *stk) 
{ 
    return (stk->top == -1); 
} 

int main (void) 
{ 
    stack_t *stk = malloc (sizeof (stack_t)); 
    node_t *head, *main_head, *temp1, *temp; 
    int i, k, n; 

    printf ("\nEnter number of list elements: "); 
    scanf ("%d", &n); 
    printf ("\nEnter value of k: "); 
    scanf ("%d", &k); 

    /* Using dummy head 'main_head' */ 
    main_head = malloc (sizeof (node_t)); 
    main_head->next = NULL; 
    /* Populate list */ 
    for (i=n; i>0; i--) 
    { 
    temp = malloc (sizeof (node_t)); 
    temp->a = i; 
    temp->next = main_head->next; 
    main_head->next = temp; 
    } 

    /* Show initial list */ 
    printf ("\n"); 
    for (temp = main_head->next; temp != NULL; temp = temp->next) 
    { 
    printf ("%d->", temp->a); 
    } 

    stk_init (stk); 

    /* temp1 is used for traversing the list 
    * temp is used for tracing the revrsed list 
    * head is used for tracing the sublist of size 'k' local head 
    * this head value is used to link with the previous 
    * sublist's tail value, which we get from temp pointer 
    */ 
    temp1 = main_head->next; 
    temp = main_head; 
    /* reverse process */ 
    while (temp1) 
    { 
    for (i=0; (temp1 != NULL) && (i<k); i++) 
    { 
     push (stk, temp1); 
     temp1 = temp1->next; 
    } 
    head = pop (stk); 
    temp->next = head; 
    temp = head; 
    while (!empty (stk)) 
    { 
     temp->next = pop (stk); 
     if (temp->next == NULL) 
     break; 
     temp = temp->next; 
    } 
    } 
    /* Terminate list with NULL . This is necessary as 
    * for even no of nodes the last temp->next points 
    * to its previous node after above process 
    */ 
    temp->next = NULL; 

    printf ("\n"); 
    for (temp = main_head->next; temp != NULL; temp = temp->next) 
    { 
    printf ("%d->", temp->a); 
    } 

    /* free linked list here */ 

    return 0; 
} 

Answer 5

Yeah, tôi chưa bao giờ được một fan hâm mộ của đệ quy, vì vậy đây là bắn của tôi lúc đó sử dụng lặp đi lặp lại:

public Node reverse(Node head, int k) { 
     Node st = head; 
     if(head == null) { 
     return null; 
     } 

     Node newHead = reverseList(st, k); 
     st = st.next; 

     while(st != null) { 
     reverseList(st, k); 
     st = st.next; 
     } 

     return newHead 

    } 


private Node reverseList(Node head, int k) { 

     Node prev = null; 
     Node curr = head; 
     Node next = head.next; 

     while(next != null && k != 1){ 
     curr.next = prev; 
     prev = curr; 
     curr = next; 
     next = next.next; 
     --k; 
     } 
     curr.next = prev; 

     // head is the new tail now. 
     head.next = next; 

     // tail is the new head now. 
     return curr; 
} 

Answer 6

Các giải pháp sau đây sử dụng thêm không gian để lưu trữ các con trỏ, và đảo ngược từng đoạn của liệt kê riêng. Cuối cùng, danh sách mới được xây dựng. Khi tôi thử nghiệm, điều này dường như bao gồm các điều kiện biên.

template <typename T> 
struct Node { 
T data; 
struct Node<T>* next; 
Node() { next=NULL; } 
}; 
template <class T> 
void advancePointerToNextChunk(struct Node<T> * & ptr,int & k) { 
int count =0; 
while(ptr && count <k) { 
    ptr=ptr->next; 
    count ++; 
} 
k=count;} 

/*K-Reverse Linked List */ 
template <class T> 
void kReverseList(struct Node<T> * & head, int k){ 
int storeK=k,numchunk=0,hcount=0; 
queue < struct Node<T> *> headPointerQueue; 
queue <struct Node<T> *> tailPointerQueue; 

struct Node<T> * tptr,*hptr; 
struct Node<T> * ptr=head,*curHead=head,*kReversedHead,*kReversedTail; 
while (ptr) { 
advancePointerToNextChunk(ptr,storeK); 
reverseN(curHead,storeK,kReversedHead,kReversedTail); 
numchunk++; 
storeK=k; 
curHead=ptr; 
tailPointerQueue.push(kReversedTail),headPointerQueue.push(kReversedHead); 
} 
while(!headPointerQueue.empty() || !tailPointerQueue.empty()) { 
    if(!headPointerQueue.empty()) { 
     hcount++; 
     if(hcount == 1) { 
      head=headPointerQueue.front(); 
      headPointerQueue.pop(); 
     } 
     if(!headPointerQueue.empty()) { 
     hptr=headPointerQueue.front(); 
     headPointerQueue.pop(); 
     } 
    } 
    if(!tailPointerQueue.empty()) { 
     tptr=tailPointerQueue.front(); 
     tailPointerQueue.pop(); 
    } 
    tptr->next=hptr; 
} 
tptr->next=NULL;} 

template <class T> void reverseN(struct Node<T> * & head, int k, struct Node<T> * & kReversedHead, structNode<T> * & kReversedTail) { 
    struct Node<T> * ptr=head,*tmp; 
    int count=0; 
    struct Node<T> *curr=head,*nextNode,*result=NULL; 
    while(curr && count <k) { 
     count++; 
     cout <<"Curr data="<<curr->data<<"\t"<<"count="<<count<<"\n"; 
     nextNode=curr->next; 
     curr->next=kReversedHead; 
     kReversedHead=curr; 
     if(count ==1) kReversedTail=kReversedHead; 
     curr=nextNode; 
    }} 

Answer 7

public class ReverseEveryKNodes<K> 
{ 
     private static class Node<K> 
     { 
     private K k; 
     private Node<K> next; 

     private Node(K k) 
     { 
      this.k = k; 
     } 
     } 
private Node<K> head; 
private Node<K> tail; 
private int size; 

public void insert(K kk) 
{ 
    if(head==null) 
    { 
     head = new Node<K>(kk); 
     tail = head; 
    } 
    else 
    { 
     tail.next = new Node<K>(kk); 
     tail = tail.next; 
    } 
    size++; 
} 

public void print() 
{ 
    Node<K> temp = head; 
    while(temp!=null) 
    { 
     System.out.print(temp.k+"--->"); 
     temp = temp.next; 
    } 
    System.out.println(""); 
} 

public void reverse(int k) 
{ 
    head = reverseK(head, k); 
} 

Node<K> reverseK(Node<K> n, int k) 
{ 
    if(n==null)return null; 

    Node<K> next=n, c=n, previous=null; 
    int count = 0; 
    while(c!=null && count<k) 
    { 
     next=c.next; 
     c.next=previous; 
     previous=c; 
     c=next; 
     count++; 
    } 
    n.next=reverseK(c, k); 
    return previous; 
} 

public static void main(String[] args) 
{ 
    ReverseEveryKNodes<Integer> r = new ReverseEveryKNodes<Integer>(); 
    r.insert(10); 
    r.insert(12); 
    r.insert(13); 
    r.insert(14); 
    r.insert(15); 
    r.insert(16); 
    r.insert(17); 
    r.insert(18); 
    r.print(); 
    r.reverse(3); 
    r.print(); 
} 
}