反转链表

反转一个单链表。

示例:

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

进阶:

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

解法1（递归）：

思路： 这位大佬有图，很清楚（链表翻转的图文讲解（递归与迭代两种实现）

java：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        if(head==null||head.next==null){
            return head;
        }
        ListNode newhead=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newhead;  
    }
}

c语言：

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

解法2：（非递归）

思路： 参考这图（[链表翻转的图文讲解（递归与迭代两种实现]

node* reverseList(node* H)
{
    if (H == NULL || H->next == NULL) //链表为空或者仅1个数直接返回
        return H;
    node* p = H, *newH = NULL;
    while (p != NULL)                 //一直迭代到链尾
    {
        node* tmp = p->next;          //暂存p下一个地址，防止变化指针指向后找不到后续的数
        p->next = newH;               //p->next指向前一个空间
        newH = p;                     //新链表的头移动到p，扩长一步链表
        p    = tmp;                   //p指向原始链表p指向的下一个空间
    }
    return newH;
}

BB一句：

思考：线性链表中P->next到底表示P结点的next域还是p结点的下一个结点呢