反转链表的2种方法-创新互联

力扣-反转链表

我们提供的服务有：成都网站设计、成都网站建设、外贸网站建设、微信公众号开发、网站优化、网站认证、黄冈ssl等。为成百上千企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的黄冈网站制作公司

是在同一个链表，不创建新的链表

最后返回head

思路1：翻转next

反转箭头即可,使前一个本应指向下一个的next，指向前一个的前一个 

注意： ①改变后找不到下一个，所以提前保存下一个的地址 ②对于当n3指到NULL时，最后一个箭头还未反转：

使n2++为NULL，结束

③当head为NULL时，最初创建n3时的head->next直接非法访问

综上

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = head->next;   //当head==NULL,这里next直接非法访问
                                        //所以开头加入判断

    while (n2)
    {
        //  翻转
        n2->next = n1;
        //  迭代向后走
        n1 = n2;
        n2 = n3;
        if (n3) // 判断n3是否为NULL，为NULL则不执行
            n3 = n3->next;
    }
    return n1;
}

思路2：头插

而在最后一个，和上面思路相同的情况

struct ListNode* reverseList2(struct ListNode* head) {
    struct ListNode* cur, *next, *newhead;
    cur = head; next = head->next;  newhead = NULL;

    while (cur)
    {
        //  头插
        cur->next = newhead;
        newhead = cur;
        //  迭代
        cur = next;
        if (next)
            next = next->next;
    }

    return newhead;
}

这里不需要判断head是否为NULL 因为cur保存head，如果head为NULL，则不会进入cur的循环

ps：不建议使用递归，因为递归需要消耗栈，如果节点过多，递归过深，则栈可能撑不住

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页标题：反转链表的2种方法-创新互联
链接分享：http://dzwzjz.com/article/diedes.html