Home Tags Posts tagged with "递归"

递归

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head){   
    //反转链表 即使用头插法;
     struct ListNode * Ahead=(struct ListNode*)malloc(sizeof(struct ListNode));//头节点;
     Ahead->next=NULL;
     struct ListNode *p=head,*q=p;//初始化;
     while(q!=NULL){//q为当前插入的点;
         p=q->next;
         q->next=Ahead->next;
         Ahead->next=q;
         q=p;
     }//头插法反转成功;
     return Ahead->next;
}
/*递归如下;
#include <stdio.h>
#include <stdlib.h>
void  reveral(struct ListNode* p, struct ListNode* q, struct ListNode* Ahead);
int main() {
    struct ListNode* l1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* head = l1;
    for (int i = 0; i < 5; i++) {
        int a;
        struct ListNode* P = (struct ListNode*)malloc(sizeof(struct ListNode));
        scanf_s(“%d”, &a);
        P->val = a;
        P->next = NULL;
        l1->next = P;
        l1 = P;
    }//创建完毕;
    struct ListNode* Ahead = (struct ListNode*)malloc(sizeof(struct ListNode));
    Ahead->next = NULL;
    struct ListNode* p = head, * q = p;//初始化;
    reveral(p, q, Ahead);
    Ahead = Ahead->next;
    for (int i = 0; i < 5; i++) {
        printf(“%2d”, Ahead->val);
        Ahead = Ahead->next;
    }
}
void reveral(struct ListNode* p, struct ListNode* q, struct ListNode* Ahead) { 
    if (q == NULL)return;
     {//q为当前插入的点;
        p = q->next;
        q->next = Ahead->next;
        Ahead->next = q;
        q = p;
      }
     reveral(p, q, Ahead);
}
*/