【GL001】数据结构&算法

一、递归案例

1.递归翻转链表（Python） 

from typing import Optional

class ListNode:
    def __init__(self, val, next: 'Optional[ListNode]' = None):
        self.val = val
        self.next = next

def reverse(head: Optional[ListNode]):
    if head is None or head.next is None:  # 递归停止的基线条件
        return head
    new_head = reverse(head.next)
    head.next.next = head	# 当前层函数的head节点的后续节点指向当前head节点
    head.next = None	# 当前head节点指向None
    return new_head

# 创建链表示例
node1 = ListNode(5)
node2 = ListNode(6)
node3 = ListNode(3)
node4 = ListNode(1)
node5 = ListNode(2)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

result = reverse(node1)
while result:
    print(result.val, end=' -> ')
    result = result.next
print('null')

2.链表逆序输出（C）

// 定义链表节点结构体
typedef struct ListNode {
    int data;   
    struct ListNode *next;
} ListNode;

// 辅助函数，用于创建新的链表节点
ListNode* createListNode(int data) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int List_nixu(ListNode L)
{
    if(L->next == NULL)
      return 1;
    List_nixu(L->next);
    printf("%d\n",L->data);
}

int main() {
    // 创建链表 1 -> 2 -> 3 -> 4 -> 5
    ListNode *node5 = createListNode(5);
    ListNode *node4 = createListNode(4);
    ListNode *node3 = createListNode(3);
    ListNode *node2 = createListNode(2);
    ListNode *node1 = createListNode(1);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    // 反转并打印链表
    List_nixu(node1);

    // 释放链表内存
    free(node1);
    free(node2);
    free(node3);
    free(node4);
    free(node5);

    return 0;
}

 3.链表区间翻转

        （1）直接法（C）

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

// 定义链表节点结构体
typedef struct ListNode
{
    int val;
    struct ListNode *next;
} ListNode;

// 创建新节点
ListNode *createNode(int val)
{
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 反转链表区间(三步走)
void reverseBetween(ListNode *head, int m, int n)
{
    if (head == NULL || head->next == NULL || m == n)
        return;

    // 1.找到m位置的节点和它的前一个节点
    ListNode *prevM = NULL; // 保存m位置的前一个节点
    ListNode *nodeM = head; // 保存m位置的节点
    for (int i = 1; i < m; i++)
    {
        prevM = nodeM;
        nodeM = nodeM->next;
    }

    // 2.反转从m到n的节点
    ListNode *prev = NULL;
    ListNode *curr = nodeM;
    ListNode *nextM = NULL;
    for (int i = m; i <= n; i++)
    {
        nextM = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextM;
    }

    // 3.将反转后的链表接回原链表
    if (prevM != NULL)
        prevM->next = prev;
    else
        head = prev;
    nodeM->next = nextM;
    return;
}

// 打印链表
void printList(ListNode *head)
{
    while (head != NULL)
    {
        printf("%d -> ", head->val);
        head = head->next;
    }
    printf("NULL\n");
}

// 释放链表内存
void free_List(ListNode *head)
{
    while (head != NULL)
    {
        ListNode *temp = head;
        head = head->next;
        free(temp);
    }
}

// 主函数
int main()
{
    // 创建链表 1 -> 2 -> 3 -> 4 -> 5
    ListNode *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    printf("Original List: ");
    printList(head);

    // 反转第2个到第4个节点
    reverseBetween(head, 2, 4);

    printf("Reversed List: ");
    printList(head);

    // 释放链表内存
    free_List(head);
    return 0;
}

        （2）递归法（python）

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverseBetween_turtle(head, left, right):
    def reverseN(head, n):
        if n == 1:
            successor = head.next
            return head, successor
        last, successor = reverseN(head.next, n - 1)
        head.next.next = head
        head.next = successor
        return last, successor

    if left == 1:
        new_head, _ = reverseN(head, right)
        return new_head
    head.next = reverseBetween_turtle(head.next, left - 1, right - 1)
    return head

# 构建测试链表
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

new_head = reverseBetween_turtle(node1, 2, 4)
while new_head:
    print(new_head.val)
    new_head = new_head.next

         （3）递归法（C）

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

// 定义链表节点结构体
typedef struct ListNode
{
    int val;
    struct ListNode *next;
} ListNode;

// 创建新节点
ListNode *createNode(int val)
{
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 递归反转链表区间
void reverseBetween_turtle(ListNode** head, int m, int n) {
    if (*head == NULL || m == n) return;
    
    if (m == 1) {
        ListNode* prev = NULL;
        ListNode* curr = *head;
        ListNode* next = NULL;
        
        for (int i = 1; i <= n; i++) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        *head = prev;
        return;
    }
    
    ListNode* prev = NULL;
    ListNode* curr = *head;
    for (int i = 1; i < m; i++) {
        prev = curr;
        curr = curr->next;
    }
    
    reverseBetween_turtle(&curr, 1, n - m + 1);
    
    if (prev != NULL) {
        prev->next = curr;
    } else {
        *head = curr;
    }
}


// 打印链表
void printList(ListNode *head)
{
    while (head != NULL)
    {
        printf("%d -> ", head->val);
        head = head->next;
    }
    printf("NULL\n");
}

// 释放链表内存
void free_List(ListNode *head)
{
    while (head != NULL)
    {
        ListNode *temp = head;
        head = head->next;
        free(temp);
    }
}

// 主函数
int main()
{
    // 创建链表 1 -> 2 -> 3 -> 4 -> 5
    ListNode *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    printf("Original List: ");
    printList(head);

    // 反转第2个到第4个节点
    reverseBetween_turtle(&head, 2, 4);

    printf("Reversed List: ");
    printList(head);

    // 释放链表内存
    free_List(head);
    return 0;
}

二、斐波那数列（C） 

#include <stdio.h>

int fun(int x)
{
    int sum = 0;
    if(x==0)
        return 0;
    if(x==1)
        return 1;
    sum=fun(x-1)+fun(x-2);
    return sum;
}

int main()
{   
    int x=10;
    int i;
    for(i=0;i<x;i++)
    printf("%d\n",fun(i));
}

三、更多》》》》》