Инвертировать каждые k узлов связанного списка - PullRequest
Новая
       0

Инвертировать каждые k узлов связанного списка

6 голосов
/ 21 августа 2011

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

Например 

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

EDIT:

Вот мой код. Я получаю только 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;

}

Любая помощь приветствуется. Спасибо.

РЕДАКТИРОВАТЬ: Я пытался реализовать алгоритм Эрана Циммермана, как показано ниже. 

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

Ответы [ 7 ]

5 голосов
/ 08 ноября 2011

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

  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;
 }
2 голосов
/ 21 августа 2011

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

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;
}
1 голос
/ 21 августа 2011

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

Причина : Вы забыли вернуть новый узел 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;
1 голос
/ 21 августа 2011

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

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.

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

, чтобы ответить относительно кода, который вы добавили:

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

0 голосов
/ 21 августа 2013 
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();
}
}
0 голосов
/ 13 июня 2012

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

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;
  }}
0 голосов
/ 21 августа 2011

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

...