リンクリストのすべてのk個のノードを逆転します

Question

技術的なインタビューの準備をしていますが、リンクリストのk個のノードをすべてリバースするためにこのプログラムを書いていません。例えば

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

編集：ここでは

が私のコードです。私は出力として6-> 5を得るだけです。

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; 

} 

何か助けていただければ幸いです。ありがとう。

EDIT：下記のようにEran Zimmerman's Algorithmを実装しようとしました。

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

私はあなたにとって最良の解決策ではないかもしれませんが、再帰が好きです。私はあなたのコードから、設計時に深く考えていることが分かります。あなたは答えから一歩足早です。

原因：再帰のケースで新しいrootノードを返すことを忘れた場合。

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

私はこのようなものだろう：

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 

をし、逆にCURRから始まる最初のk個の要素を反転させる機能です。

これは、最もエレガントな、または最も効率的な実装ではないかもしれませんが、動作し、非常に簡単です。

には、追加したコードについてお答えします

はあなたが絶えず進められている前に、返されました。リストの先頭に戻る必要があります。

Answer 3

（私はこれが単独でリンクされたリストであると仮定しています。）あなたはそれがwhileループでk回の一時的なポインタ（nodekそれを呼び出すことができます）と進歩を維持することができます。これはO（k）になります。これで、リストの先頭とサブリストの最後の要素へのポインタが得られました。ここで逆にするには、O（1）である頭部から削除し、O（1）であるnodekに追加します。すべての要素に対してこれを行うので、これは再びO（k）です。 rootをnodekに更新し、nodekのwhileループをもう一度実行して（nodekの新しい位置を取得する）、この全体のプロセスをやり直してください。途中でエラーチェックをすることを忘れないでください。 このソリューションは、O（1）余分なスペースだけでO（n）で実行されます。

Answer 4

ここに擬似コードがあります。

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

私はこのコードのデモ実装を行いました。厄介な実装のために恩赦。これはkの任意の値に対して機能します。各kサイズのセグメントは内側のループで別々に反転され、異なるセグメントは内側のループに入る前に外側のループで互いにリンクされます。 tempはkサイズのサブリストの最後のノードをトレースし、headは次のサブリストの次の値を保持し、それらをリンクします。反転を行うには、明示的なスタックが使用されます。

#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

はええ、私は再帰のファンだったことがないので、ここで反復を使用して、それで私のショットは次のとおりです。

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

次のソリューションは、ポインタを格納するための余分なスペースを使用し、それぞれのチャンクを反転させます別にリストしてください。最後に、新しいリストが作成されます。私がテストしたとき、これは境界条件をカバーするように見えました。

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