Обратить все k узлов связанного списка

Я готовлюсь к техническому интервью, и я застреваю в написании этой программы, чтобы перевернуть все 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 && countlink; root->link=prev; prev=root; root=temp; } if(temp!=NULL) noode->link=recrev(temp,c); else return prev; } 

Любая помощь приветствуется. Благодарю.

EDIT: Я попытался реализовать алгоритм Эрана Циммермана, как показано ниже.

 struct node* rev(struct node* root,int c) { struct node* first=root,*prev,*remaining=NULL; int count=0; while(first!=NULL && countlink; 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 && countdata); // 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; } в struct node* rev(struct node* root,int c) { struct node* first=root,*prev,*remaining=NULL; int count=0; while(first!=NULL && countlink; 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 && countdata); // 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; } 

Мне нравится recursion, хотя это может быть не лучшее решение. Я могу видеть из вашего кода, что вы думаете, что это глубоко, когда вы его разрабатываете. Вы всего в одном шаге от ответа.

Причина . Вы забываете вернуть новый 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; 

Да, я никогда не был поклонником рекурсии, так что вот мой выстрел в нее, используя итерацию:

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

Вот псевдокод.

 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  #include  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) && (inext; } 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; } 

Я бы сделал что-то вроде этого:

 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 

а reverse – функция, которая меняет первые k элементов, начиная с curr.

это может быть не самая элегантная или наиболее эффективная реализация, но она работает и довольно проста.

ответить на добавленный код:

вы вернулись назад, который постоянно продвигается. вы должны вернуть начало списка.

(Я предполагаю, что это список, связанный по отдельности.) Вы можете сохранить временный указатель (позвоните ему nodek ) и nodek его k раз в цикл while. Это займет O (k). Теперь у вас есть указатель на начало списка и на последний элемент подписок. Чтобы обратить вспять здесь, вы удаляете из головы, которая является O (1), и добавляйте к nodek который является O (1). Сделайте это для всех элементов, так что это O (k) снова. Теперь обновите root до nodek и снова запустите цикл while на nodek (чтобы получить новую позицию nodek ) и повторите весь этот процесс еще раз. Не забудьте выполнить проверку ошибок на этом пути. Это решение будет работать на O (n) только с дополнительным пространством O (1).

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

 template  struct Node { T data; struct Node* next; Node() { next=NULL; } }; template  void advancePointerToNextChunk(struct Node * & ptr,int & k) { int count =0; while(ptr && count next; count ++; } k=count;} /*K-Reverse Linked List */ template  void kReverseList( struct Node * & head, int k){ int storeK=k,numchunk=0,hcount=0; queue < struct Node *> headPointerQueue; queue  *> tailPointerQueue; struct Node * tptr,*hptr; struct Node * 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  void reverseN(struct Node * & head, int k, struct Node * & kReversedHead, structNode * & kReversedTail ) { struct Node * ptr=head,*tmp; int count=0; struct Node *curr=head,*nextNode,*result=NULL; while(curr && count next; curr->next=kReversedHead; kReversedHead=curr; if(count ==1 ) kReversedTail=kReversedHead; curr=nextNode; }} 
 public class ReverseEveryKNodes { private static class Node { private K k; private Node next; private Node(K k) { this.k = k; } } private Node head; private Node tail; private int size; public void insert(K kk) { if(head==null) { head = new Node(kk); tail = head; } else { tail.next = new Node(kk); tail = tail.next; } size++; } public void print() { Node 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 reverseK(Node n, int k) { if(n==null)return null; Node next=n, c=n, previous=null; int count = 0; while(c!=null && count r = new ReverseEveryKNodes(); 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(); } } в public class ReverseEveryKNodes { private static class Node { private K k; private Node next; private Node(K k) { this.k = k; } } private Node head; private Node tail; private int size; public void insert(K kk) { if(head==null) { head = new Node(kk); tail = head; } else { tail.next = new Node(kk); tail = tail.next; } size++; } public void print() { Node 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 reverseK(Node n, int k) { if(n==null)return null; Node next=n, c=n, previous=null; int count = 0; while(c!=null && count r = new ReverseEveryKNodes(); 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(); } }