刷题笔记:力扣第206题-反转链表

1.看评论区有朋友总结出了一个简单明了的思路原链表:1→2→3→4(prenull)1 null←1 2→3→4(pre1)2 null←1←2 3→4(pre2)3 null←1←2←3 4(pre3)4 null←1←2←3←4(pre4)每次都将原链表的next指向新链表的末尾并且都记录上一次操作的节点pre写出的完整代码如下1. /** 2. * Definition for singly-linked list. 3. * struct ListNode { 4. * int val; 5. * struct ListNode *next; 6. * }; 7. */ 8. struct ListNode* reverseList(struct ListNode* head) { 9. // 空链表直接返回NULL 10. if (head NULL) return NULL; 11. 12. // cur遍历当前处理节点初始指向头节点 13. struct ListNode* cur head; 14. // pre保存上一个节点反转后作为当前节点后继初始为空 15. struct ListNode* pre NULL; 16. while (cur ! NULL){ 17. // tmp临时保存下一个节点防止断链丢失后续链表 18. struct ListNode* tmp cur-next; 19. // 当前节点指向前面节点完成反转 20. cur-next pre; 21. // tmp为空说明已经遍历到原链表最后一个节点就是反转后的新头节点 22. if (tmp NULL){ 23. return cur; 24. } 25. // pre更新为当前节点作为下一轮的前驱 26. pre cur; 27. // cur移动到原下一个节点继续反转 28. cur tmp; 29. } 30. 31. return cur; 32. }还可以继续简化不需要if (tmp NULL)返回值从cur改为pre即可最后一次pre的指向的节点便是新链表的头结点。这样一来就连一开始的特出情况判断if (head NULL) return NULL也可以删去了。2.上述代码使用的是迭代法循环下面这种写法是递归法自己调用自己1. /** 2. * Definition for singly-linked list. 3. * struct ListNode { 4. * int val; 5. * struct ListNode *next; 6. * }; 7. */ 8. // 递归反转链表辅助函数pre为前一个节点cur为当前处理节点 9. struct ListNode* reverse(struct ListNode* pre, struct ListNode* cur){ 10. // 递归终止条件当前节点为空pre就是反转后的头节点 11. if (cur NULL) return pre; 12. // 临时保存cur原本的下一个节点防止断链 13. struct ListNode* tmp cur-next; 14. // 将当前节点指向前面节点完成局部反转 15. cur-next pre; 16. // 更新前驱节点为当前节点供下一层递归使用 17. pre cur; 18. // 递归处理下一个节点 19. return reverse(pre, tmp); 20. } 21. 22. // 链表反转入口函数 23. struct ListNode* reverseList(struct ListNode* head) { 24. // 初始前驱传NULL当前节点传链表头调用递归反转 25. return reverse(NULL, head); 26. }这种写法与第一种思路一模一样只是进行了递归改写。