目录

引言
代码实现
算法流程图
小结

引言

最近有一些碎片时间,利用碎片时间在力扣刷一刷算法题,碰到了一道题,算法过程的子算法需要反转部分链表,看了看题解,觉得这个链表翻转的算法很有趣,也是一种有趣的思路,记录一下。

代码实现

还是直接上代码吧

csharp
public class ListNode { public int val; public ListNode next; public ListNode(int val = 0, ListNode next = null) { this.val = val; this.next = next; } } public ListNode ListNodeReverse(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; }

算法讲解:

  1. 初始状态:prev 指向 nullcurr 指向原始链表的头节点(head)。

  2. 核心逻辑:

    通过循环逐个处理节点,每次迭代中:

    ①:先保存当前节点的下一个节点(避免指针丢失)。

    ②:将当前节点的 next 指针反向指向 prev(完成一次反转)。

    ③:移动 prevcurr 指针,继续处理下一个节点。

  3. 终止条件:当 curr 指向 null 时,说明所有节点已处理完毕,prev 此时指向反转后链表的头节点。

算法流程图

根据上述的算法,我手绘了算法流程图,以此方便更快的理解上述算法: 链表的反转.jpg

小结

该流程的时间复杂度为 O(n)(需遍历所有节点),空间复杂度为 O(1)(仅使用 3 个指针变量),是反转链表的最优解法之一

本文作者:Peter.Pan

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!