时间戳

首页 > 解决方案 > 如何递归地反转带有双指针的链表

c - 如何递归地反转带有双指针的链表

问题描述

目标是将系列整数 1 2 3 4 5 反转为 5 4 3 2 1。

这是结构定义：

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode;         // You should not change the definition of ListNode

typedef struct _linkedlist
{
    int size;
    ListNode *head;
} LinkedList;

我有一个使用这个调用的函数 RecursiveReverse(&(ll.head));

void RecursiveReverse(ListNode **ptrHead)
{
    ListNode *curr,*q;
    curr = *ptrHead; //same as ll.head

    if(curr == NULL)
    {
        return;
    }

    if(curr->next == NULL)
    {
        *ptrHead = curr;
        return;
    }
    RecursiveReverse(&(curr->next));
    q = curr->next;
    q->next = curr;
    curr->next = NULL;
}

在这一步，如果我的输入是 1 2 3 ，输出只有 1。任何帮助表示赞赏！

标签： cpointerslinked-list

解决方案

这段代码正在尝试，我将大小固定为 5

#include <stdio.h>
#include <stdlib.h>

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode;         // You should not change the definition of ListNode

struct _listnode* RecursiveReverse(struct _listnode* head)
{
    struct _listnode *temp = head;
    struct _listnode *curr = head;
    struct _listnode *prev = NULL;
    struct _listnode *next = NULL;
    int count = 0;

    // Reverses the first k nodes iteratively
    while (curr != NULL && count < 5){
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
            count++;
    }

    if (next != NULL) temp->next = RecursiveReverse(next);
    return prev;
}

int main() {
   struct _listnode* head = NULL; 
   struct _listnode* item2 = NULL; 
   struct _listnode* item3 = NULL; 
   struct _listnode* item4 = NULL; 
   struct _listnode* item5 = NULL; 

   struct _listnode* reverse = NULL; 

   head = (struct _listnode*)malloc(sizeof(struct _listnode));
   item2 = (struct _listnode*)malloc(sizeof(struct _listnode));
   item3 = (struct _listnode*)malloc(sizeof(struct _listnode));
   item4 = (struct _listnode*)malloc(sizeof(struct _listnode));
   item5 = (struct _listnode*)malloc(sizeof(struct _listnode));

   item5->item = 5;
   item5->next = NULL;

   item4->item = 4;
   item4->next = item5;

   item3->item = 3;
   item3->next = item4;

   item2->item = 2;
   item2->next = item3;

   head->item = 1;
   head->next = item2;

   reverse = RecursiveReverse(head);

   while (reverse != NULL) { 
      printf(" %d ", reverse->item); 
      reverse = reverse->next; 
   }

   return 0;
}

推荐阅读