链表的反转

链表的翻转常见的解决方法分为迭代和递归两种。

github源码
递归和迭代两个函数在SingleLinkedList文件夹中的SingleLinkedList.c中实现。

假设创建好的链表结构如下：

迭代方式

static int reverseList1(SingleLinkedList *This){
    Node *p = This->This->next;
    if (p == NULL || p->next == NULL) return -1;
    Node *temp = NULL, *newH = NULL;
    while (p != NULL){
        temp = p->next;
        p->next = newH;
        newH = p;
        p = temp;
    }
    This->This->next = newH;
    return 0;
}

代码执行过程分析：
开始：

第1步：

第2步：

第3步：

第4步：

第5步：

第6步：

结束：

递归方式

//递归方式
static Node *ReverseList2(Node *head){
    if (head == NULL || head->next == NULL){
        return head;
    }else{
        Node *temp = head->next, *newH = NULL;
        head->next = NULL;
        newH = ReverseList2(temp);
        temp->next = head;
        return newH;
    }
}

static int reverseList2(SingleLinkedList *This){
    Node *p = This->This->next;
    if (p == NULL || p->next == NULL) return -1;
    This->This->next = ReverseList2(p);
    return 0;
}

代码执行过程分析：
第1层递归：

第2层递归：

第3层递归：

返回到第2层：

返回到第1层：

结束：

运行测试

编译：

gcc SingleLinkedList.c testSingleLinkedList.c -o testSingleLinkedList

运行testSingleLinkedList，结果：

list is empty:1
0 1 2 3 4 5 6 7 8 9
list is empty:0
list length:10
reverse1 list :              //迭代方式
9 8 7 6 5 4 3 2 1 0
reverse2 list :             //递归方式
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
the elem of index 3 is 13
modify the elem of index 3 to 31
10 11 12 31 14 15 16 17 18 19
insert elem 25 to index 5
10 11 12 31 14 25 15 16 17 18 19
delete elem 16 of index 7
10 11 12 31 14 25 15 17 18 19
the index of 14 is 4
pop elem 19
10 11 12 31 14 25 15 17 18