Odwróć co k węzłów połączonej listy

Question

Przygotowuję się do wywiadu technicznego i utknąłem w pisaniu tego programu, aby odwrócić każde k węzłów połączonej listy.

Na przykład

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

EDIT:

Oto mój kod. Dostaję tylko 6-> 5 jako wynik.

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; 

} 

Każda pomoc jest doceniana. Dzięki.

EDYCJA: Próbowałem wprowadzić algorytm Eran Zimmermana, jak poniżej.

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

Lubię rekurencję, choć może nie być najlepszym rozwiązaniem. Z Twojego kodu widzę, że myślisz o tym głęboko podczas projektowania. Jesteś tylko o krok od odpowiedzi.

Przyczyna: Zapominasz zwrócić nowy węzeł root w swojej walizce rekurencyjnej.

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

chciałbym zrobić coś takiego:

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 

i odwrócić to funkcja, która odwraca pierwsze k elementów, począwszy od Curr.

To może nie być najbardziej elegancka lub najbardziej wydajna implementacja, ale działa i jest dość prosta.

odpowiedzieć dotyczące kodu dodanego:

powróciłeś poprzednie, które jest stale zaawansowany. powinieneś zwrócić początek listy.

Answer 3

(Zakładam, że jest to pojedynczo połączonej listy.) Można utrzymać tymczasowy wskaźnik (pozwala wywołać nodek) oraz zaliczkę to k razy w pętli while. To zajmie O (k). Teraz masz wskaźnik do początku listy i do ostatniego elementu podlisty. Aby odwrócić tutaj, usuń z głowy, która jest O (1) i dodaj do nodek, która jest O (1). Zrób to dla wszystkich elementów, więc znowu jest to O (k). Teraz zaktualizuj root do nodek i ponownie uruchom pętlę while na nodek (aby uzyskać nową pozycję nodek) i powtórz cały proces ponownie. Pamiętaj, aby po drodze sprawdzić błędy. To rozwiązanie będzie działać w O (n) z dodatkową przestrzenią O (1).

Answer 4

Oto pseudo kod.

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

Wykonałem wersję demo tego kodu. Wybacz za niechlujną implementację. To zadziała dla dowolnej wartości k. Każdy segment o rozmiarze k jest odwracany osobno w wewnętrznej pętli, a różne segmenty są połączone ze sobą w zewnętrznej pętli przed wejściem do wewnętrznej. temp śledzi ostatni węzeł podlisty o rozmiarze k, a head przechowuje następną wartość następnej podlisty i łączymy je. Stosuje się jawny stos do odwrócenia.

#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

Tak, ja nigdy nie byłem fanem rekursji, więc tutaj jest mój strzał na niego przy użyciu iteracji:

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

Poniżej rozwiązanie wykorzystuje dodatkową przestrzeń do przechowywania wskaźników i odwraca każdy klocek lista osobno. Na koniec budowana jest nowa lista. Kiedy testowałem, wydawało mi się, że pokrywa to warunki brzegowe.

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