旋转链接列表C

我目前正在解决列表和函数的求和问题，并且我遇到了这个问题，即将一个链表逆时针旋转k。这里是相同旋转链接列表C

void rotate_k(struct list *node,int k) 
{ 
    int count=0; 
    struct list *knode,*ptr=node; 
    while(ptr!=NULL && count < k) 
    { 
     ptr=ptr->next; 
     count++; 
    } 
    knode=ptr; 
    while(ptr->next!=NULL) 
    { 
     ptr=ptr->next; 
     } 
    ptr->next =node; 
    node=knode->next; 
    knode->next=NULL; 
    }

代码比方说，如果输入是1-> 2-> 3-> 4-> 5-> 6且k = 4。输出应该是5-> 6-> 1-> 2-> 3-> 4，但代码给出输出1-> 2-> 3-> 4-> 5。需要帮助:)

来源

2013-09-27 user2714823

什么也调试器说什么？ – pm100

认为需要对列表做些什么。找到第k个元素;使它成为新的头部，并使旧的尾巴成为老头。我没有看到代码做最后2部分。同时返回新的头 – pm100

第二个while循环进入列表末尾，ptr-> next =节点使尾部指向旧头。 node = knode-> next使5个新列表的头部 – user2714823

你没有修改原始列表（node参数）

struct list *rotate_k(struct list *node,int k) 
{ 
    int count=0; 
    struct list *knode,*ptr=node; 
    while(ptr!=NULL && count < k) 
    { 
     ptr=ptr->next; 
     count++; 
    } 
    knode=ptr; 
    while(ptr->next!=NULL) 
    { 
     ptr=ptr->next; 
    } 
    ptr->next =node; 
    node=knode->next;  
    knode->next=NULL; 

    return knode; //<-- THIS IS THE NEW LIST 
}

此外，knode->next=NULL奇怪;你应该在knode之前的（是）节点处（这是从结果中删除6的节点）。

来源

2013-09-27 18:32:00 SJuan76

返回应该返回的节点，而不是knode对吗？ – user2714823

从我的代码（和结果）中读取，'knode'指向'5'，这是您期望的元素。无论如何测试它。 – SJuan76

SJuan的方法是正确的，但是如果你想在不使用返回值的情况下做到这一点，那么你需要为节点使用双指针。请记住，C会将您传递给函数的变量的副本。如果原始根节点是一个指针（我假设它是），则需要制作一个指向指针的指针，否则只是对根节点指针的副本进行更改，而不是实际的根节点指针。

void rotate_k(struct list **node, int k) 
{ 
    int count = 0; 
    struct list *knode, *ptr = *node; 
    while(ptr != NULL && count < k) 
    { 
     ptr = ptr->next; 
     count++; 
    } 
    knode = ptr; 
    while(ptr->next != NULL) 
    { 
     ptr = ptr->next; 
    } 
    ptr->next = *node; 
    *node = knode->next;  
    knode->next = NULL; 
}

来源

2013-09-27 19:09:54 Nate

void rotate_list_right(listnode** head, int k) 
    { 
    if(!head || !*head) 
     { 
     printf("\nrotate_list_right: empty list = so return \n"); 
     return; 
     } 
    if(k < 1) 
     { 
     printf("\nrotate_list_right:invalid input: k must be >= 1 \n"); 
     return; 
     } 

    listnode* post = *head; 
    listnode* curr = *head; 

    /* move post by k nodes */ 
    while(k--) 
     { 
     post = post->next; 
     if(!post) /* k is bigger than length of the list */ 
      { 
      printf("\nrotate_list_right:invalid input: k must be smaller than list size \n"); 
      return; 
      } 
     } 

    /* move curr to kth-last node */ 
    while(post->next) 
     { 
     curr = curr->next; 
     post = post->next; 
     } 

    /* currs' next is new header */ 
    listnode* tmp = *head; 
    *head = curr->next; 
    curr->next = 0; 

    //join post 
    post->next = tmp; 
    }

来源

2014-07-09 19:47:01 Viren

旋转链接列表C

回答

相关问题