Leetcode题库剑指 Offer 24. 反转链表(头插法 c实现)

Leetcode题库剑指 Offer 24. 反转链表(头插法 c实现),第1张

文章目录
  • 思路
    • 方法1:头插法
    • 方法2:递归
  • 代码
    • 头插法

思路 方法1:头插法

ret为返回链表的头部
head_last指向下一个加入ret的节点
每次将head取出使用头插法将其插入ret
然后head=head_last, head_last=head->next
如此循环直至head_last为NULL
举例:
head_last: 2 -> 3
head: 1 #将head插入ret链表
ret: 1

head: 2 -> 3
head_last: 3
head: 2 #将head插入ret链表
ret: 2 -> 1

head: 3
head_last: NULL
head: 3 #将head插入ret链表
ret: 3 -> 2 -> 1

head_last: NULL跳出循环

方法2:递归

使用递归,递归到head链表尾部,随着每一层递归的返回记录当前的head节点到新链表中,最后也能达到反转链表的效果

举例:
第一层:
head: 1 -> 2 -> 3
head->next 不为空
继续递归

第二层:
head: 2 -> 3
head->next 不为空
继续递归

第三层:
head: 3
head->next 为空
返回将当前节点加入新链表(ret = 3 -> NULL)

返回第二层:
返回将当前节点加入新链表(ret = 3 -> 2 -> NULL)

返回第一层:
返回将当前节点加入新链表(ret = 3 -> 2 -> 1 -> NULL)

代码 头插法
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *ret,*head_last;
    while(head != NULL){
        head_last = head->next;
        head->next = ret;
        ret = head;
        if(head_last == NULL) break;
        head = head_last;
    }
    return ret;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1295259.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-10
下一篇 2022-06-10

发表评论

登录后才能评论

评论列表(0条)

保存