【链表】反转单链表

题目链接

做题时思路：（已解决，糟烂算法）

1. 先求出链表长度。设定两个指针p1和p2。p1为慢指针，p2为快指针。设立int值n为size-1
2. 让p2后移n位，找到对应结点。交换值
3. p1后移一位，将n-2。将p2重新设为p1，再次让p2后移，直到n==1或==0

做题时思路2：运用递归

1. 写一个函数，作为我们的递归函数。向函数中传入两个结点。递归结束条件为传入结点的指针域为NULL

代码：（未通过）

void switchVal(struct ListNode* pointer1, struct ListNode* pointer2) {
    int temp = pointer1->val;   
    pointer1->val = pointer2->val;
    pointer2->val = temp;
}

int reverse(struct ListNode* pointer1, struct ListNode* pointer2) {
    while(pointer2->next != NULL)
        reverse(pointer1, pointer2->next);
    switchVal(pointer1, pointer2);
    pointer1 = pointer1->next;
    return 0;
}

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL || head->next==NULL)
        return head;
    reverse(head,head->next);
    return head;
}

官方思路一：用栈解决

算法思路：

1. 创建一个栈，将结点中元素一个一个入栈
2. 从栈顶开始一个一个出栈，新出栈的结点构成一个新的链表

代码：