最近有一些碎片时间,利用碎片时间在力扣刷一刷算法题,碰到了一道题,算法过程的子算法需要反转部分链表,看了看题解,觉得这个链表翻转的算法很有趣,也是一种有趣的思路,记录一下。
还是直接上代码吧
csharppublic 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;
}
算法讲解:
初始状态:prev
指向 null
,curr
指向原始链表的头节点(head
)。
核心逻辑:
通过循环逐个处理节点,每次迭代中:
①:先保存当前节点的下一个节点(避免指针丢失)。
②:将当前节点的 next
指针反向指向 prev
(完成一次反转)。
③:移动 prev
和 curr
指针,继续处理下一个节点。
终止条件:当 curr
指向 null
时,说明所有节点已处理完毕,prev
此时指向反转后链表的头节点。
根据上述的算法,我手绘了算法流程图,以此方便更快的理解上述算法:
该流程的时间复杂度为 O(n)(需遍历所有节点),空间复杂度为 O(1)(仅使用 3 个指针变量),是反转链表的最优解法之一
本文作者:Peter.Pan
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!